[Database/기초] Index 저장 자료구조와 복합키 저장 방식

DB 에서 사용하는 자료구조는?

DB들은 기본적으로 B+tree를 사용한다

B-tree

https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/

자료구조 설명

이진 탐색트리를 개선한 자료구조이다
기본적으로 모든 leaf노드가 동일한 level에 있다. 또한 부모노드(내부노드)도 key값과 value값을 가지고있는다. (최악 시간복잡도가 log(n)으로 동일하게 보장된다는 뜻이다.즉 최소 시간 = 최악 시간이 항상 보장되는것이 아니다)
따라서 leaf노드까지 탐색을 진행하지 않고 탐색이 끝날수도있다.
2개이상의 자식을 가질수도 있다.
부모노드가 N개를 값을 가지고있다면 자식노드는 최대 N+1개의 노드를 가지고있을 수 있다

범위 탐색

A이상B이하 범위탐색을 진행해야 할시 A값을 찾으려 부모노드부터 자식까지 탐색(분기 탐색) 1회 B값을 찾으려 부모노드부터 자식 노드까지 탐색 총 2회를 진행하게된다.
O(log n + k × log n)
→ k개 찾을 때마다 다시 탐색 필요 가능성 있음

B+tree

https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/

자료구조 설명

Mysql, Postgre, Oracle등 메이저 DB들이 Index를 저장하는 방식이다.
여기서는 Linked-List가 추가등장한다.(메모리 소모가 더 많지만 탐색 속도가 증가한다. 어디에나 장단점은 있는법)
따라서 B+tree는 최악의 시간 복잡도 = 최선의 시간 복잡도가 항상 같음을 보장한다.(logn)
B-tree와 비슷해보이나 부모노드(중간노드)들이 key값만 가지고있고 실제 데이터 Value는 가지고있지 않는다.
leaf노드들이 데이터 전부를 가지고 있으며 이들은 정렬된 상태로 Linked-List연결이 되어있다. 이는 리프노드가 값을 (key, value, nextKey) 식으로 저장하고있다. 따라서 다음 값을 찾을때 리스트를 보고 key값을 찾을수 있다.

범위 탐색

A이상 B이하 범위탐색을 진행할때 A를 찾을때 분기탐색 1회를 진행하고 Linked-list를 보고 순차 탐색이 가능해진다.
O(log n + k)
→ 1번만 트리 탐색, 나머지는 순차 탐색
B-tree와 비교해보면 시간차를 볼수있다. 물론 메모리를 더쓴다는걸 기억하자.

그럼 이제 복합키는 저장방식이 뭘까?

CREATE INDEX idx_user_id_age ON user(id, age);

이렇게 생긴 인덱스가 있다고 가정하자. Primary Index는 id, Secondary Index는 age이다.(복합키가 3,4개 더많아도 Primary빼고는 다 Second다.  알파메일 ㄷㄷ)

                         [ (2,30) ]                        ← root (depth 0)
                           /     \
              [ (1,30) ]           [ (3,40) ]               ← 내부 노드 (depth 1)
             /        \            /         \
[ (1,20)(1,25)(1,30) ]→[ (2,22)(2,30)(2,40) ]→[ (3,18)(3,40) ]→[ (3,50)(4,10)(4,20)(4,30) ]
                               ↑             ↑             ↑
                             리프 노드 (depth 2, Linked List 연결됨)

저장방식은 모든 DB가 동일하다. 부모노드에서 아래로 탐색하면서 primary index로 정렬되고 leaf에서 primary에 따라 정렬된 second들을 찾아볼 수 있다.

그럼 second가 여러개라면? (A, B ,C 순서)

똑같이 순서대로 정렬되며 마지막에는 A, B가 같은값이며 C로 정렬된 노드들을 만날수 있다.
이는 즉 A, B, C의 순서를 잘 지켜서 쿼리를 만들어야한다는 얘기다.
 
각 DB종류의 옵티마이저 마다 복합인덱스 사용방식이 다르니 참고해보자.

DB별 차이

 

항목	MySql	PostSql	Oracle
인덱스 구조	B+ Tree	B+ Tree	B* Tree (B+ Tree 확장형)
리프 연결	✅ 있음	✅ 있음	✅ 있음
Index Skip Scan 지원	⭕ 지원	❌ 미지원	⭕ 지원
복합키 선두 누락 조건	B, C 단독 조건 가능(조건부)	A 없으면 못 씀	B, C 단독 조건 가능
Index Merge 지원	⭕ (조건부 OR 조합)	⭕ (Bitmap 방식으로 조합)	⭕ (Bitmap Index 가능)
정확도 높은 실행계획	중간 정도	매우 보수적	상당히 공격적 (자동 최적화 많음)

어차피 Index의 순서는 성능에 영향을 주니까 어떤식으로 저장하는지 왜 순서가 중요한지 이해하고 사용하면 된다.