[MySQL] Index [2] — 인덱스 자료 구조 (Hash Table)
[1] [MySQL] Index [1] — 인덱스 사용 배경, 인덱스와 디스크 I/O
[2] [MySQL] Index [2] — 인덱스 자료 구조 (Hash Table)
| 인덱스 자료 구조 — Hash Table
먼저 소개할 자료 구조는 Hash 알고리즘을 활용한 Hash Table 이다. Hash Table 은 Map 타입이므로 Key : Value 구조를 갖는데, 여기서 인덱스가 Key 에 해당하고 Value 가 데이터 또는 데이터를 가리키고 있는 포인터 (논리 또는 물리 주소) 로 볼 수 있다.
우선 Hash Table 자료 구조의 가장 큰 장점은 탐색 과정이 상수 시간에 처리된다는 점이다. 따라서 단 건 조회를 하는 경우 해당 데이터를 매우 빠르게 탐색할 수 있다는 장점이 있다.
다만 해시 알고리즘 구조 상 항상 탐색 과정에서 상수 시간을 보장할 수 없다. 이러한 이유는 해시 충돌로 인한 문제 때문인데, [ 그림 4 ] 와 같이 Hash Function 의 인풋 값은 무한하지만 반대로 일정한 길이의 값을 갖는 해시 값 (또는 해시 코드)은 유한한 값을 갖게 되므로 결과적으로 [ 그림 5 ] 와 같이 서로 다른 인풋 값의 해시 값이 동일한 해시 충돌 현상이 일어날 수 있다.
해시 충돌이 일어나면 [ 그림 3 ] 의 버킷 내부에서 연결 리스트를 활용해서 해시 코드가 같은 값을 관리할 수 있는데, 이 경우 데이터 탐색 시 O(N = 한 버킷에서 관리되는 데이터 수) 이 된다.
인덱스에 해시 알고리즘을 기반으로한 해시 테이블 구조를 사용 했을 때, 단 건 조회에는 (평균적으로) 매우 좋은 성능을 가질 것으로 판단할 수 있다.
전방(Prefix) 일치와 같이 값의 일부만 검색하거나 범위를 검색할 때는 해시 인덱스를 사용할 수 없다.
다만 위 인용 내용과 같이 값의 일부만 검색하는 경우, 일반적으로 완전히 다른 해시 값을 갖게 되므로 인덱스 값의 일부분만 활용해 검색할 수 없다는 특징이 있다. 또한 각 인덱스가 해시 함수를 거쳐 해시 값을 갖게 되는 구조로 동작하므로 인덱스로 활용되는 컬럼에 대해 정렬이 오름 또는 내림차순과 같은 정렬이 적용되지 않아 범위 검색에 있어서 단 건 검색에 비해 상대적으로 비효율적이다.
일반적으로 DBMS 에서 전방 일치 기반 검색 또는 >, >=, <, <= 와 같은 부등호가 포함된 쿼리를 비교적 자주 사용한다는 점에서 인덱스 자료 구조로써 Hash Table 이 주로 사용되기에는 여러 제한이 있다는 것을 이해할 수 있다.
다음 글에서는 DBMS 에서 인덱스 자료 구조로 주로 사용하는 B-Tree 에 대해서 다룰 예정이다.
| Reference
Real MySQL 8.0 | 4장 아키텍처
Real MySQL 8.0 | 8장 인덱스
Hash function — Wikipedia
인덱스 정리 및 팁DB Index 입문
