목록확장성 해싱 (1)

홍카나의 공부방

[데이터베이스] 저장 구조 - 해싱 방법, 저장 구조의 비교

해싱 방법 해시 함수를 이용해서 키 값 input에 대한 목표 레코드의 주소로 한 번에 찾아가는 방법이다. 직접 탐색에는 힙이나 B+tree에 비해서 훨씬 빠를 것이다. 여러 해싱 방법 중에서 버킷 해싱이라는 방법이 있다. 여기서 버킷은 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역을 지칭한다. 각 버킷은 연결 리스트와 같은 자료 구조로 구현된다. 버킷 해싱은 키를 넣으면 해시 함수를 거쳐서 버킷 주소를 알려주는 구조다. 만약 해시 함수가 출력 값을 고르게 분포하지 않을 경우, 서로 다른 데이터가 같은 버킷에 할당되는 충돌 현상이 발생한다. 해시 충돌은 어쩔 수 없이 벌어지는 현상이다. 해시 함수의 출력 값이 무한하지 않기 때문이다. 이러면 특정 버킷이 오버플로우 될 수 있..
Data Engineering/Database 2023. 5. 18. 16:55
이전 Prev 1 Next 다음