인덱스 알고리즘

1. 인덱스의 핵심 자료구조

대부분의 데이터베이스 인덱스는 트리 기반 또는 해시 기반 구조를 사용합니다.

(1) B-Tree / B+Tree

MySQL(InnoDB), Oracle, PostgreSQL 등 대부분의 관계형 DB에서 기본 인덱스 알고리즘으로 사용.

B+Tree가 가장 흔함.

루트 → 브랜치 → 리프 노드 구조

리프 노드에 실제 데이터(혹은 레코드 포인터)가 정렬된 상태로 연결됨 (Linked List).


장점

범위 검색(RANGE SCAN) 지원 (WHERE age BETWEEN 20 AND 30)

정렬된 순회가 빠름 (ORDER BY, GROUP BY)


시간 복잡도: 검색/삽입/삭제 ≈ O(log N)



---

(2) Hash Index

MySQL Memory 엔진, 일부 NoSQL에서 사용.

Key → 해시 함수 → 버킷 → 레코드 포인터

장점

정확히 일치하는 검색(=)에서 매우 빠름.


단점

범위 검색, 정렬, LIKE 'abc%' 불가능.


시간 복잡도: 평균 O(1) (해시 충돌 많을 시 O(N)까지 느려질 수 있음).



---

(3) GiST / GIN / R-Tree (특수 인덱스)

PostgreSQL 같은 고급 DB에서 사용.

GiST (Generalized Search Tree)
다양한 사용자 정의 인덱스를 구현할 수 있는 확장형 구조.

GIN (Generalized Inverted Index)
풀텍스트 검색, 배열 검색 등에 최적화.

R-Tree
좌표/지리 정보 같은 다차원 데이터 인덱싱.



---

2. 내부 동작 방식 요약

1. 인덱스 생성 시, 지정된 컬럼 기준으로 데이터가 정렬된 상태로 인덱스 트리/해시가 만들어짐.


2. 검색 시

B+Tree: 루트에서 리프까지 탐색 → 해당 키의 레코드 포인터로 이동.

Hash: 해시 함수 계산 → 버킷에서 키 확인 후 레코드 포인터로 이동.



3. 삽입/삭제 시

B+Tree: 트리 균형 유지 위해 split/merge 발생.

Hash: 버킷에 삽입, 충돌 시 체이닝 또는 오픈 어드레싱 처리.





---

3. 비교 정리

알고리즘 특징 장점 단점 사용 사례

B+Tree 정렬된 트리 구조 범위 검색, 정렬 지원 삽입/삭제 시 리밸런싱 비용 대부분의 PK/일반 인덱스
Hash 키 기반 해싱 동등 검색 빠름 범위 검색 불가 메모리 DB, 캐시, Key-Value
GiST 일반화 트리 커스텀 인덱스 확장 가능 구현 복잡 PostgreSQL 특수 인덱스
GIN 역색인 텍스트/배열 검색 강점 업데이트 느림 Full-text search
R-Tree 다차원 트리 공간/좌표 검색 최적화 범용성 낮음 GIS, 공간 DB



---

👉 요약하자면:
대부분의 RDBMS는 B+Tree 인덱스를 기본으로 사용하며, 상황에 따라 Hash나 **특수 인덱스(GiST, GIN, R-Tree)**를 추가적으로 활용합니다.


-