[20230811 TIL] 해시 인덱스와 B-Tree 인덱스 차이

해시 인덱스와 B-Tree 인덱스는 데이터베이스에서 사용되는 인덱스 알고리즘 중 두 가지 주요 유형이다.

#해시 인덱스
해시 인덱스는 보통 해시 테이블을 사용하여 구현된다. 해시 테이블은 해시 함수에 따라 키-값 쌍을 저장하는 자료구조다.

해시 인덱스는 해시 함수를 이용하여 데이터의 값을 해시 키로 변환하고, 해당 해시 키에 대응하는 데이터를 인덱스화하는 방식이다. 간단히 말해, 데이터 값과 그 값에 해당하는 인덱스가 직접 매핑되어 저장된다.

장점으로,
  - 등값 검색에 매우 빠르며, 데이터의 양에 무관하게 검색 속도가 일정하다.
  - 해시 값으로 인덱싱되기 때문에 빠른 검색 성능을 제공한다.

단점으로,
  - 범위 검색에는 적합하지 않습니다. 연속된 값들에 대한 범위 검색이 비효율적이다.
  - 충돌(Collision) 문제: 서로 다른 데이터 값이 같은 해시 키를 가질 수 있습니다. 이를 처리하기 위한 방법이 필요하다.
  - 인덱스 크기가 크고, 메모리 사용이 비효율적일 수 있다.

#B-Tree 인덱스:
B-Tree는 균형 이진 트리의 변형으로, 각 노드는 정해진 수의 자식 노드를 가지고 있다. 이로써 높은 밀도의 인덱스 구조를 구성할 수 있다.

B-Tree는 균형 잡힌 트리로서, 데이터의 정렬된 구조를 유지하면서 효율적인 검색과 삽입, 삭제를 지원한다. B-Tree 인덱스는 트리의 각 노드가 키 값을 가지고 있으며, 각 노드는 정해진 수의 자식 노드를 가질 수 있다.

장점으로,
  - 범위 검색에 효율적입니다. 키 값의 정렬된 구조로 인해 범위 검색이 빠르다.
  - 인덱스의 높은 밀도: 노드가 여러 키를 가지고 있기 때문에, 인덱스 크기가 작아진다.
  - 충돌 문제가 해시 인덱스보다 적다.

단점으로,
  - 등값 검색에는 일정한 성능을 보장하지 않는다. 최악의 경우 트리의 높이에 따라 검색 성능이 결정된다.