B+트리를 활용하여 DB 인덱싱하기

 

 오늘은 데이터베이스 성능 최적화에 사용되는 인덱싱 기법에 대해서 소개하려고 합니다. 인덱싱으로 쓰이는 자료구조인 B+트리에 대해 알아보고, 구조와 동작하는 방식에 대해 살펴보겠습니다.

 

 

---

 

목차

1. B+트리 개념 및 특성
2. 트리의 구조
3. 분석

 

 

---

 

#1 B+트리 개념 및 특성

 B+트리란 데이터베이스에서 데이터를 빠르고 효율적으로 관리할 수 있게 해주는 자료구조입니다. 데이터베이스에서 인덱싱을 할 때 가장 많이 사용되는 방식이에요. 그렇다면 B+트리를 많이 사용하는 이유가 뭘까요?

<그림 1> B+ 트리 구조

 

시간복잡도가 O(log n)으로 빠르다!

 

 B+ 트리는 내부 노드가 자식 노드를 여러 개를 가질 수 있는 높은 팬아웃을 가지고 있기 때문입니다. 자식 노드가 많아지다 보니, 더 많은 데이터를 노드에 할당할 수 있게 되고, 이로 인해 트리의 높이는 매우 낮게 유지가 됩니다. 따라서 탐색, 삽입, 삭제 등의 효율이 매우 높은 편입니다.

 

 

범위 검색이 간편하다!

 B+ 트리는 모든 데이터들을 내부 노드(Internal Node)가 아닌 리프 노드들(Leaf Nodes)에 저장을 하고, 이들을 서로 이중 연결 리스트 형태로 연결합니다. 리프 노드들이 모두 정렬이 되어있기 때문에 O(K)의 시간 복잡도가 소요됩니다. 리프 노드를 찾는 시간까지 포함하면 O(log n + K)로 굉장히 효율적입니다.

 

 

자동으로 인덱싱이 가능하다!

 B+트리는 사용도 간편합니다! MySQL, Oracle과 같은 관계형 데이터베이스뿐만 아니라 MongoDB와 같은 NoSQL 데이터베이스에서 B+트리를 자동으로 구현해 줍니다. 따로 B+트리 구조를 구현할 필요 없이 명령어만으로 자동 인덱싱이 가능하다고 합니다.

 

 CREATE INDEX name ON table (column);

 

 위의 CREATE INDEX ~ ON ~ 구문을 사용하면 B+트리를 활용하여 자동으로 인덱스를 만들어줘요. 실무하게 유용하게 사용될 것 같습니다. :)

 

 

---

 

#2 트리의 구조

<그림 2> B+트리 예시

 

 B+트리는 <그림 2> 처럼 모든 인덱스 value의 중앙값을 루트(root)로 지정합니다. 그 이유는 트리의 높이를 최소화하고 트리의 균형을 맞추어 효율성을 극대화하기 위해서입니다.

 

 Root 지정 후, 노드에 키를 삽입하며 데이터를 저장합니다. 그러나 삽입 과정에서 리프 노드가 가득차는 경우가 발생할 수 있는데요. 이러한 경우에는 노드를 분할해야 합니다. B+트리는 자식노드가 여러 개일 수 있다며? 근데 가득 차는 경우가 발생한다고??라고 생각하실 수 있어요. 이론상 맞아요. 하지만 디스크와 메모리 크기, 데이터의 크기 등을 고려해야 하기 때문에 리프노드 수에 리밋이 존재하므로, 인덱스가 늘어날수록 노드를 분할하며 트리의 높이가 높아지고, 성능도 조금씩 하락하게 됩니다.

 

 모든 데이터를 저장한 후에는 리프노드들끼리 연결리스트로 연결합니다. 따라서 100부터 200까지의 데이터를 찾는 것과 같은 범위 탐색이 빠르고, 순차 접근을 사용하기 때문에 리프노드의 모든 데이터를 한번에 탐색이 가능합니다.

 

 

B-트리와 차이점은 무엇인가?

 

 B+트리는 B-트리와는 다르게 내부 노드(Internal Node)를 제외한 리프 노드(Leaf Node)에만 데이터를 저장합니다. B+트리는 내부노드에 오직 탐색과 접근을 위해 키와 포인터만 저장해요. 이러한 접근을 하고 범위 탐색을 더 빠르게 하기 위해 리프 노드들끼리 연결리스트로 연결되어있다는 차이점이 존재합니다. 따라서 B+트리는 범위 검색과 탐색에서 유리하고, B-트리는 모든 노드에 데이터가 저장되어 있기 때문에 데이터 탐색에 유리합니다.

 

 

---

 

#3 분석

 

데이터베이스 인덱싱은 탐색 성능을 끌어올리기 위한 하나의 기법으로, 필수적으로 사용해야합니다.사용해야 합니다. 인덱싱을 할 때 목적에 따라 B+트리와 B-트리를 적절히 선택하고, 인덱스를 너무 많이 추가하는 경우 최대치의 성능을 발휘하지 못한다는 점을 항상 주의하며 사용해야 합니다.

 

 

 

이미지 출처

https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC

https://cs186berkeley.net/sp21/resources/static/notes/n03-B+Trees.pdf