TIL) 해시와 탐색에 대해서

데이터베이스 해시 파일과 해시 인덱스를 공부하는 도중 이 내용은 정리하면 좋을 거같아서 TIL을 작성하려고 해요

머리 속 끄집어내기

수 많은 데이터 중에서 우리가 찾는 데이터를 빠르게 찾고 싶습니다.

옷장에 필요한 옷을 찾을 때에도 어디 쯤에 있는지 알기만 하더라도 찾는 시간은 줄일 수 있습니다

해시 파일은 동일합니다.

탐색키를 산술적 연산을 통해 나온 결과를 버킷에 저장하게 됩니다.

탐색키를 몇번이나 멱등성으로 동일한 결과가 나오기에 저장할 때 뿐만 아니라 탐색할 때에도 필요하게 됩니다.

데이터베이스에서 버킷은 디스크 I/O와 동일한 데이터 전송 단위인 4KB(설정에 따라 다름)으로 관리합니다.

해시 파일은 데이터를 저장할 때 레코드를 그대로 버킷에 저장하는 방식입니다.

옷을 보관할 때 봄, 여름, 가을, 겨울옷으로 나누어 보관하면 계절이 지나면 해당 계절별 옷에서 필요한 옷을 꺼내면 됩니다.

겨울 옷은 두꺼워서 옷 봉지가 많아질 것이고, 한 두개가 아닐 수 있습니다.

그러면 찾아야하는 옷 봉지가 그만큼 많아진다는 이야깁니다.

해시 파일의 단점이 이런 거과 같습니다.

특정 버킷에 레코드가 가득차게 되는 것을 버킷 오버플로우라고 합니다. 겨울 옷 봉지에 가득 찬거죠

그러면 다음 봉지를 꺼내서 보관하듯 새로운 버킷을 꺼내 보관하게 됩니다.

그리고 겉에 이렇게 적겠죠 ?

겨울 옷 1, 겨울 옷 2

버킷은 오버플로우가 발생하면 버킷내 한번 다 찾고 없으면 다음 버킷을 또 찾아야합니다.

이게 어디서 동작하냐? 디스크에서 발생하게 됩니다.

디스크에서 데이터를 읽을 수 없습니다. 메모리 까지 로드하고 읽어야합니다.

해시 파일을 사용하는 이유는 필요한 자료를 어느정도 위치에 있는지 빠르게 확인하여 빠르게 찾는 방법입니다.

무한한 입력 범위에 비해 해시는 제한된 버킷에 저장하기에 오버 플로가 발생할 수 있으며 곧 성능 저하가 됩니다.

해시 오버플로우가 발생하는 이유는 많은 데이터가 저장되는 이유도 있지만 레코드 데이터가 커진다면 버킷도 금방 차게 됩니다.

테이블에 데이터를 저장한다고 해볼게요

해시파일로 관리되는 테이블이 있다면 필드가 추가되는 경우 버킷이 가득차 성능 저하가 발생할 수 있습니다.

그러면 테이블 필드를 추가하는 것이 유연하지 못하게 됩니다.

그러니 우리는 인덱스 엔트리를 버킷에 저장하고 인덱스 엔트리를 찾으면 인덱스로 디스크 블록을 찾아 조회를 하는 방법입니다.

이런 방식을 사용하면 테이블은 탐색 키를 기준으로 버킷이 저장되고 한번 더 찾는 과정이 생기지만 그래도 해시 파일보다 테이블 구조에 유연할 수 있습니다.

마찬가지로 탐색 키가 커지면 해시 파일과 같은 버킷 오버플로우가 발생할 일이 많아지며 데이터가 많아지면 많아질 수록 해시 오버플로우는 피할 수 없습니다.

게다가 버킷은 내부가 순차적 탐색이므로 효율적인 탐색 방식이 아닙니다.

프로그래밍 언어에서는 이 과정을 트리 구조와 진화된 해시를 사용한 방식으로 해결하게 됩니다.

1. HashMap은 내부에 해시 충돌이 발생하게 되면 처음에는 연결 리스트이지만 이후 정렬 트리를 사용하며
2. Redis는 자신들의 특화된 Hash 구조를 활용하여 빠른 조회가 가능하도록 합니다.

해시 충돌과 충돌 해결방안

해시 충돌이 발생되면 체이닝 방식과 오픈 어드레싱 방식이 있습니다.

체이닝 방식은 자바 HashMap이 이 방식을 선택했습니다.

동일한 해시 버킷에 충돌이 발생하면 체이닝을 통해 동일한 해시를 사용하는 방법입니다.

장점은 해시 충돌이 발생하지 않는 이상 버킷 탐색에 대한 추가 연산이 발생하지 않습니다.

오픈 어드레싱 방식은 해시 충돌이 발생하면 다음 버킷에 데이터를 저장하는 방식입니다.

이걸 어떤 연산을 사용하여 건너뛸것인지 따라 다릅니다.

해시 충돌이 발생한 이후로 사용중인 버킷에 접근하게 되면 다음 탐색이나 저장을 위한 연산을 하는 시간이 필요하게 될것입니다.

체이닝 방식은 동적 메모리 영역을 사용하고 메모리를 확장하여 사용할 수 있다면 장점이 될 수 있습니다.

다만 제한된 메모리 내에서 해시 충돌을 해결해야한다면 체이닝 방식은 제한된 해결 방안이라고 생각합니다.

오픈 어드레싱 방식은 제한된 메모리 영역에서 데이터를 꽉꽉 채우는 방식이며 남은 공간을 어떻게 사용할 것인지

그리고 데이터 삭제를 하는 경우 해당 버킷이 비어있다는 것을 표시하는 마킹 과정이 생기게 됩니다.

효율적인 메모리 공간을 사용해야한다면 오픈 어드레싱 방식이 적합할 수 있습니다.