[CS/Database] DBMS에서의 B-Tree 인덱스

우리가 데이터를 찾을 때에는 인덱스가 필요하다.

 

인덱스는 특정 열 값을 가진 행을 빠르게 찾는 데에 사용되는 자료구조이다.

 

인덱스가 없다면 테이블 전체를 순차적으로 스캔해야하므로, O(N)의 시간복잡도가 발생하며, 이에 대하여 인덱스를 통해 O(logN)으로 개선할 수 있다.

 

그렇다면 대표적인 RDBMS에서 채택하는 인덱스에 대하여 알아보자.

 

 

B-Tree 인덱스

 

B-Tree(Balaced Tree)는 이진 탐색 트리를 확장한 자기 균형 트리 자료구조로, 다음과 같은 특징을 가진다.

 

1. 차수(Order)인 m의 정의 : m차 B-Tree, 이는 한 노드가 가질 수 있는 최대 자식의 수가 m개라는 의미이다
2. 키의 개수: 각 노드는 최소 ⌈m/2⌉-1개 (위는 반올림), 최대 m-1개의 키를 가진다 (키에 대해선 루트 노드 제외)
3. 자식의 개수: 각 노든느 최소 ⌈m/2⌉개, 최대 m개의 자식을 가진다
4. 균형 유지: 모든 리프 노드는 같은 레벨에 존재한다.
5. 정렬 보장: 노드 내의 키들은 항상 정렬된 상태를 유지한다.
6. 탐색 복잡도: O(logN)의 시간복잡도로 검색, 삽입, 삭제가 가능하다.

위와 같은 특징들을 지키기 때문에 B-Tree가 Balanced의 특징을 가질 수 있는 것이다.

 

더 자세한 자료 구조에 대한 것은 이전 포스트에서 기록해두었으니 연산에 대해서는 해당 게시글을 참조하자!

https://kite-u.tistory.com/264

[자료구조] B-Tree

 

 

 

 

 

 

이러한 B-Tree는 한계점이 존재한다.

리프 노드 간의 연결이 없기 때문에 범위 검색 시에는 꼭 부모 노드로 재귀적으로 올라가야한다는 점이다.

 

 

당장 위의 경우만 보아도, 해당 하이라이트를 범위 검색을 하려면 옆의 노드로 이동하려고 할 때 다시 부모 노드로 올라간 뒤에 다시 순회해야한다.

 

디스크 I/O가 추가로 발생하여 성능이 저하된 것이다.

 

 

 

그래서 확장 된 것이 B+Tree 자료구조이다.

 

 

 

B+Tree

 

B+Tree는 B-Tree의 변형으로, 범위 검색과 순차 접근을 최적화한 구조이다.

 

다음과 같은 특징을 가진다.

1. 리프 노드 데이터 집중 : 모든 실제 데이터(레코드 포인터)는 리프 노드에만 존재한다.
2. 내부 노드의 역할 변경 : 내부 노드는 인덱스 역할만 수행한다(라우팅 정보)
3. 리프 노드 연결 : 같은 레벨의 리프 노드들이 연결리스트(Linked List)로 연결 -> 확실히 범위 검색에 대한 효율성을 높이기 위한것으로 보임
4. 중복 키 허용 : 내부 노드의 키가 리프 노드에도 중복 저장됨

 

이러한 특징들이 어떻게 범위 검색의 효율을 높이는지에 대하여도 더 알아보자

 

 

B+Tree의 장점

범위 검색 최적화

위의 사진과 같이 Tree가 구성되어있다고 해보자.

SELECT * FROM users WHERE age BETWEEN 58 AND 90;

시작 지점이 58일 때, 이 58을 O(logN)으로 찾은 후에
리프 노드의 연결 리스트를 따라 순차 스캔만으로도 범위 검색이 완료된다.

리프 노드끼리는 연결되어있기 때문에 가능한 것이다.

추가적인 트리 순회가 불필요하다.

 

더 높은 팬아웃(Fanout)

내부 노드에 데이터 포인터가 없어 더 많은 키를 저장하는 것이 가능하다.

트리의 높이가 낮아져서 디스크의 I/O가 감소한다.

 

순차 접근 효율성

리프 노드만 순회하면 되므로 Full Scan 시에도 효율적이다.

캐시 친화적인 순차접근의 패턴인 것이다.

이러한 장점들로 인하여 3대 RDBMS의 경우에는 B+Tree를 채택하고 있다.

 

 

 

B+Tree의 삽입

B+Tree의 삽입 연산에 대해서도 간단히 확인해보자.

 

B-Tree 계열답게 최대 키의 개수가 정해져있다.

우선은 리프 노드 위치를 탐색(O(logN))하면,
해당 리프 노드에 키를 삽입한다.

근데 만약 노드에 대한 키의 개수가 최대 키를 넘었다고 치면(= 최대 자신의 개수인 m-1개를 초과할 경우),
이에 대하여 키를 분할해야한다.

ex) m=3

[5, 10, 15] → 최대 2개 초과
↓
중간값(10)을 부모로 승격
↓
[5] ← 부모[10] → [15]

 

이렇게 반복을 해도 균형이 유지된다.

최악의 경우에는 O(logN)의 분할이 발생할 수 있긴하다.

 

B+Tree의 제거

대체적으로 DBMS는 논리적 삭제(Soft Delete)를 이용한다고한다. 그렇기 때문에 삭제의 연산에 대해서는 다루지 않겠다.

 

정리

간단하게 정리해보자면 다음과 같다.

 

특징	B-Tree	B+Tree
데이터 위치	모든 노드	리프 노드만
범위 검색	비효율적	매우 효율적
노드 연결	없음	리프 노드 연결됨
팬아웃	상대적으로 낮음	높음
캐시 효율성	보통	우수

 

또한 B+Tree가 B-Tree보다 유리한 경우는 다음과 같다.

• 범위 검색이 빈번한 경우 (BETWEEN, >=, <=)
• 정렬된 결과가 필요한 경우 (ORDER BY)
• 순차 스캔이 필요한 경우
• 대부분의 OLTP(Online Transaction Processing) 워크로드

 

 

그러나 일반적인 인덱스들이 그러하듯이, 검색에 최적화인 인덱스는 쓰기 성능을 저하시킨다. (삽입/삭제/수정 시 인덱스도 갱신)
과도한 인덱스는 오히려 성능 저하를 유발하기 때문에 무조건적으로 좋은 것은 없다.

---

REF

• https://workat.tech/core-cs/tutorial/b-tree-and-b-plus-trees-in-dbms-gzzjplg15e4q
• https://www.youtube.com/watch?v=MuZ-Mx0N-dA&t=1058s