DBMS의 해싱: 정적 및 동적 해싱 기술

DBMS의 해싱이란 무엇입니까?

DBMS에서 해싱은 인덱스 구조를 사용하지 않고 디스크에서 원하는 데이터의 위치를 ​​직접 찾아내는 기술이다. 해싱 방법은 원래 값을 사용하는 대신 더 짧은 해시 키를 사용하여 특정 항목을 검색하는 것이 더 빠르기 때문에 데이터베이스의 항목을 인덱싱하고 검색하는 데 사용됩니다. 데이터는 이러한 레코드가 저장된 메모리 위치에 해시 함수를 적용하여 주소가 생성된 데이터 블록 형태로 저장됩니다. 데이터 블록 또는 데이터 버킷.

해싱이 필요한 이유는 무엇입니까?

다음은 해싱 방법을 적용해야 하는 DBMS의 상황입니다.

  • 거대한 데이터베이스 구조의 경우 모든 레벨에서 모든 인덱스 값을 검색하기 어렵고 원하는 데이터를 얻으려면 대상 데이터 블록에 도달해야 합니다.
  • 해싱 방법은 원래 값을 사용하는 대신 더 짧은 해시 키를 사용하여 특정 항목을 검색하는 것이 더 빠르기 때문에 데이터베이스의 항목을 인덱싱하고 검색하는 데 사용됩니다.
  • 해싱은 인덱스 구조를 사용하지 않고 디스크에 있는 데이터 레코드의 직접 위치를 계산하는 이상적인 방법입니다.
  • 이는 사전을 구현하는 데에도 유용한 기술입니다.

해싱의 중요한 용어

다음은 해싱에서 사용되는 중요한 용어입니다.

  • 데이터 버킷 – 데이터 버킷은 레코드가 저장되는 메모리 위치입니다. 저장 단위라고도 합니다.
  • : DBMS 키 관계(테이블)에서 행(튜플)을 식별하는 데 도움이 되는 속성 또는 속성 집합입니다. 이를 통해 두 테이블 간의 관계를 찾을 수 있습니다.
  • 해시 기능: 해시 함수는 모든 검색 키 세트를 실제 레코드가 있는 주소에 매핑하는 매핑 함수입니다.
  • 선형 프로빙 – 선형 프로빙은 프로브 간의 고정된 간격입니다. 이 방법에서는 이전 레코드를 덮어쓰는 대신 사용 가능한 다음 데이터 블록을 사용하여 새 레코드를 입력합니다.
  • XNUMX 차 프로빙– 새 버킷 주소를 결정하는 데 도움이 됩니다. 원래 계산에서 제공된 시작 값에 XNUMX차 다항식의 연속 출력을 추가하여 프로브 사이에 간격을 추가하는 데 도움이 됩니다.
  • 해시 인덱스 – 데이터 블록의 주소입니다. 해시 함수는 심지어 com에 대한 간단한 수학 함수일 수도 있습니다.plex 수학 함수.
  • Double 해싱 -Double 해싱은 충돌 문제를 해결하기 위해 해시 테이블에 사용되는 컴퓨터 프로그래밍 방법입니다.
  • 버킷 오버플로: 버킷 오버플로 상태를 충돌이라고 합니다. 이는 모든 정적 기능이 작동해야 하는 치명적인 단계입니다.

해싱 기술의 유형

SQL 해싱 방법/기술에는 주로 두 가지 유형이 있습니다.

  1. 정적 해싱
  2. 동적 해싱

정적 해싱

정적 해싱에서 결과 데이터 버킷 주소는 항상 동일하게 유지됩니다.

따라서 say에 대한 주소를 생성하면 학생_ID = 10 해싱 함수 사용 모드(3), 결과 버킷 주소는 항상 다음과 같습니다. 1. 따라서 버킷 주소에는 변경 사항이 표시되지 않습니다.

따라서 이 정적 해싱 방법에서는 메모리의 데이터 버킷 수가 항상 일정하게 유지됩니다.

정적 해시 함수

  • 레코드 삽입: 새 레코드를 테이블에 삽입해야 하는 경우 해시 키를 사용하여 새 레코드에 대한 주소를 생성할 수 있습니다. 주소가 생성되면 해당 위치에 자동으로 기록이 저장됩니다.
  • Searching: 레코드를 검색해야 할 경우 동일한 해시 함수를 사용하여 데이터가 저장되어야 하는 버킷의 주소를 검색하는 데 도움이 되어야 합니다.
  • 기록 삭제: 해시 함수를 사용하면 먼저 삭제하려는 레코드를 가져올 수 있습니다. 그런 다음 메모리에서 해당 주소에 대한 레코드를 제거할 수 있습니다.

정적 해싱은 다음과 같이 더 세분화됩니다.

  1. 오픈 해싱
  2. 해싱을 닫습니다.

해싱 열기

오픈 해싱 방법에서는 이전 데이터를 덮어쓰는 대신 사용 가능한 다음 데이터 블록을 사용하여 새 레코드를 입력합니다. 이 방법은 선형 프로브라고도 합니다.

예를 들어, A2는 삽입하려는 새 레코드입니다. 해시 함수는 주소를 222로 생성합니다. 그러나 이미 다른 값이 사용하고 있습니다. 이것이 시스템이 다음 데이터 버킷(501)을 찾고 여기에 A2를 할당하는 이유입니다.

해싱 열기
오픈 해시 작동 방식

해싱 닫기

클로즈 해싱 방식에서는 버킷이 가득 차면 동일한 해시에 대해 새 버킷이 할당되고 결과는 이전 버킷 다음에 연결됩니다.

동적 해싱

동적 해싱은 데이터 버킷이 요청 시 동적으로 추가 및 제거되는 메커니즘을 제공합니다. 이 해싱에서 해시 함수는 많은 수의 값을 생성하는 데 도움이 됩니다.

순서형 인덱싱과 해싱의 차이점

다음은 인덱싱과 해싱의 주요 차이점입니다.

파라미터 주문 인덱싱 해싱
주소 저장 메모리의 주소는 기본 키라고 불리는 키 값에 따라 정렬됩니다. 주소는 항상 키 값에 대한 해시 함수를 사용하여 생성됩니다.
퍼포먼스 해시 파일의 데이터가 증가하면 감소할 수 있습니다. 성능을 저하시키는 (삽입/삭제/업데이트) 작업이 수행되면 데이터를 정렬된 형식으로 저장합니다. 해싱 성능은 데이터가 지속적으로 추가되고 삭제될 때 가장 좋습니다. 그러나 데이터베이스가 거대하면 해시 파일 구성 및 유지 관리 비용이 더 많이 듭니다.
사용 데이터 범위 검색에 선호됩니다. 즉, 특정 범위에 대한 검색 데이터가 있을 때마다 이 방법이 이상적인 옵션입니다. 이는 검색 키를 기반으로 특정 레코드를 검색하려는 경우 이상적인 방법입니다. 그러나 검색 키에 해시 함수가 있는 경우에만 제대로 작동합니다.
메모리 관리 삭제/업데이트 작업으로 인해 사용되지 않은 데이터 블록이 많이 있게 됩니다. 이러한 데이터 블록은 재사용을 위해 공개될 수 없습니다. 그렇기 때문에 정기적인 메모리 관리가 필요합니다. 정적 및 동적 해싱 방법에서는 메모리가 항상 관리됩니다. 버킷 오버플로도 완벽하게 처리되어 정적 해싱을 확장합니다.

충돌이란 무엇입니까?

해시 충돌은 데이터 세트에 있는 두 개 이상의 데이터로부터 결과적인 해시가 동일한 위치에 잘못 매핑되는 상태입니다. 해시 테이블.

해싱 충돌을 처리하는 방법은 무엇입니까?

해시 충돌을 방지하는 데 사용할 수 있는 두 가지 기술이 있습니다.

  1. 재탕: 이 방법은 레코드가 있어야 할 빈 슬롯을 찾을 때까지 지속적으로 적용되는 보조 해시 함수를 호출합니다.
  2. 쇠사슬: 연결 방법은 키가 동일한 값으로 해시된 항목의 연결 목록을 작성합니다. 이 방법을 사용하려면 각 테이블 위치에 추가 링크 필드가 필요합니다.

요약

  • In DBMS, 해싱은 인덱스 구조를 사용하지 않고 디스크에서 원하는 데이터의 위치를 ​​직접 검색하는 기술이다.
  • 해싱 방법은 원래 값을 사용하는 대신 더 짧은 해시 키를 사용하여 특정 항목을 검색하는 것이 더 빠르기 때문에 데이터베이스의 항목을 인덱싱하고 검색하는 데 사용됩니다.
  • 데이터 버킷, 키, 해시 함수, 선형 프로빙, ​​2차 프로빙, ​​해시 인덱스, Double 해싱(Hashing), 버킷 오버플로(Bucket Overflow)는 해싱에 사용되는 중요한 용어입니다.
  • 해싱 방법에는 두 가지 유형이 있습니다. 1) 정적 해싱 2) 동적 해싱
  • 정적 해싱에서 결과 데이터 버킷 주소는 항상 동일하게 유지됩니다.
  • 동적 해싱은 데이터 버킷이 요청 시 동적으로 추가 및 제거되는 메커니즘을 제공합니다.
  • 메모리의 인덱싱 주소는 중요한 값에 따라 정렬되는 반면 해싱 주소는 항상 키 값에 대한 해시 함수를 사용하여 생성됩니다.
  • 해시 충돌은 데이터 세트에 있는 두 개 이상의 데이터에서 나온 결과 해시가 해시 테이블의 동일한 위치에 잘못 매핑되는 상태입니다.
  • 재해싱과 연결은 해싱 충돌을 방지하는 데 도움이 되는 두 가지 방법입니다.