[데이터베이스] B-Tree 인덱스와 B+Tree 인덱스

B-Tree 인덱스와 B+Tree 인덱스

B-Tree와 B+Tree는 데이터베이스 인덱스에서 많이 사용되는 자료구조이다. 특히 데이터베이스 시스템에서 빠른 검색, 삽입, 삭제가 가능하도록 설계되어있다. 두 자료구조는 유사하지만, 몇 가지 중요한 차이점이 있다.

 

B-Tree 구조란?

인덱스에 대해 알기 위해서는 먼저 B-Tree 자료구조를 알아야 한다.

B-Tree는 자식 2개 만을 갖는 이진 트리(Binary Tree)를 확장하여 N개의 자식을 가질 수 있도록 고안된 것이다. 그리고 좌우 자식 간의 균형이 맞지 않을 경우에는 매우 비효율적이라, 항상 균형을 맞춘다는 의미에서 균형 트리(Balanced Tree)라고 불린다.

 

B-Tree의 핵심은 항상 정렬된 구조로 있다는 것이다.

 

B-Tree 인덱스

• B-Tree 인덱스는 B-Tree 자료구조를 사용한 데이터베이스 인덱싱 방식이다.
• 데이터베이스에서는 검색, 정렬, 삽입, 삭제를 빠르게 수행하기 위해 B-Tree 인덱스를 사용한다.

.

특징

• 모든 노드는 최소 (m/2)개, 최대 m개의 자식을 가질 수 있다. (m은 트리의 차수).
• 데이터는 내부 노드와 리프 노드 모두에 저장된다.
• 탐색, 삽입, 삭제의 시간 복잡도는 O(log n)이다.

 

B+Tree

B+Tree는 B-Tree의 확장된 버전으로, 특히 데이터베이스 인덱싱에 최적화되어 있다.

B+Tree에서는 모든 데이터가 리프 노드에만 저장된다.내부 노드는 탐색을 위한 키만을 저장하고, 실제 데이터는 리프 노드에 있다. 리프 노드들은 Linked List 형태로 연결되어 있어 **범위 검색(range search)**에 유리하다.

B+Tree 인덱스

• 데이터 검색 성능을 최적화하기 위해 사용되는 인덱싱 구조이다. 이는 B+Tree 자료구조를 기반으로 하며, 특히 범위 검색, 정렬 및 순차적 데이터 접근에서 뛰어난 성능을 제공한다.

특징

• 내부 노드는 데이터 대신 인덱스 키만을 저장한다. 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다. (cache hit를 높일 수 있음)
• 리프 노드들은 연결 리스트로 연결되어 있어, 순차적인 탐색이 쉽다.
• 리프 노드에서만 데이터를 저장하기 때문에, 탐색 시 리프 노드까지 도달해야한다.
• 데이터의 삽입, 삭제 시에도 트리의 균형을 유지하며, 시간 복잡도는 O(log n)이다.

 

 

 

출처 : https://mangkyu.tistory.com/286