[Database]B+Tree, B*Tree

목차

 

지난 글에는 DB 인덱싱에 대한 소개와 그때 사용하는 자료구조인 B-Tree에 대해 적었다.

 

2023.03.20 - [Development/Database] - [Database]Index에 대하여 + B-Tree

[Database]Index에 대하여 + B-Tree

 

요약하자면 인덱싱이란 원하는 데이터를 빨리 찾을 수 있도록 테이블 외부에 별도의 색인을 생성하는 작업이며

 

B-Tree란 이를 저장하기 위해 사용되는, 이진트리의 확장버전이라 할 수 있다.

 

추가로 B-Tree는 최악의 경우에도 언제나 O(logN)의 시간복잡도를 보장하며,

 

모든 노드에 데이터를 가리키는 값이 중복 없이, 정렬이 끝난 상태로 저장된다.

 

B+Tree

 

하지만 이런 B-Tree에도 몇 가지 단점이 존재하는데, 몇 가지만 가져오면 아래와 같다.

 

• 노드의 크기 고정 - 예를 들어 지난 글의 3차 B-Tree의 경우 각 노드는 최대 3-1=2 개의 값 만을 가질 수 있다. 만약 이 크기를 벗어난 값을 가질 경우 노드를 분할하고 합치며 구조를 변경해야 한다. 이는 물론 효율적인 검색을 위한 제약조건이지만, 지난 글에 그려져 있듯이 복잡하고 비용이 많이 든다.
• 구현 난이도 - 트리의 구조를 시키며 삽입과 삭제를 수행하는 것은 복잡하고 어렵다. 데이터의 크기가 커질수록 심해진다.
• 키 값의 중복 - 중복 데이터가 발생해 검색 속도가 느려질 가능성이 있다.
• 범위탐색 효율성 - 키 값이 연속적이지 않을 경우 범위 검색의 성능이 많이 떨어진다.

실제로 나도 B-Tree에 대해 공부하고 그림을 그리면서도 이게 무슨 소린가 잘 이해가 되지 않았으니.

 

어쨌거나 이런 단점을 극복하기 위해 B-Tree를 개선한 것이 B+Tree이다.

 

실제 데이터베이스 인덱싱은 높은 확률로 B+Tree로 이루어져 있다고 하는데, 간단히 알아보자.

 

더 빠르고 효율적인 검색을 위해 B+Tree는 아래와 같은 차이점을 갖는다.

 

• 데이터는 전부 정렬 후 리프 노드에만 저장하고, 내부 노드는 키 값만을 저장한다.
  
  
  • 이는 내부 노드와 리프 노드의 역할을 분리하고, 트리의 높이를 낮추는 효과를 가져온다.
• 리프 노드끼리는 연결 리스트(Linked List)로 연결되어 있다.
  
  
  • 이는 인접 노드를 탐색할 경우 루트에서 다시 시작해야 하는 B-Tree에 비해 장점이 된다.
  • 따라서 이 두 가지 특징으로 인해 B+Tree는 상당히 빠른 탐색 속도를 가지게 된다.
• 키 값의 중복을 허용하지 않는다. 이는 검색 속도의 증가로 나타난다.

추가로 위와 같은 특징이자 장점 때문에 대용량 데이터베이스의 인덱스 구현에 많이 사용된다고 한다.

 

하지만 이런 B+Treee도 만능은 아니라서 단점이 존재한다. 대략 아래와 같다.

 

• 리프 노드에만 데이터가 존재하기 때문에 삽입/삭제 시 추가적인 비용 발생.
• 하나의 데이터를 인덱싱 하기 위해 여러 블록에 걸쳐 I/O 수행. 불필요한 연산 추가 가능성

 

B*Tree

 

B*Tree 역시 B-Tree의 변형이다.

 

B-Tree에서 발생하는 빈번한 노드 분할 및 병합 문제를 해결하기 위해 고안되었으며

 

데이터베이스의 크기가 작거나 I/O가 빈번하게 발생하는 경우 유리하다.

 

특징은 아래와 같다.

 

• 내부 노드 역시 데이터를 저장하는 데 사용된다.
• 리프 노드의 개수가 고정되어 있지 않다. 따라서 그 사용률에 따라 트리의 재구조화가 발생한다.
• 위와 같은 이유 때문에 노드의 분할/병합의 횟수가 줄어들며 트리의 높이가 매우 낮아진다.
• 즉, B-Tree의 효율성을 유지하면서도 노드 분할 문제를 해결한 구조이다.

하지만 B*Tree는 B-Tree보다도 구현이 복잡하기 때문에 특정한 상황에서만 사용된다고 한다.