B+Tree

 

 

 

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만,

B-Tree는 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 

이러한 단점을 개선시킨 자료구조가 B+Tree임

 

[자료구조] 그림으로 알아보는 B-Tree

 

 

 

---

 

 

B+Tree

 

 

B-Tree

 

 

B+Tree

 

 

🔳 모든 key, data 가 리프노드 (leaf node) 에 모여있고,

       리프노드가 아닌 노드에서는 자식 포인터만 저장함 (=리프노드를 제외하고 데이터를 저장하지 않음)

 

       > 하나의 노드에 더 많은 포인터를 가질 수 있기 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있음 

          반드시 특정 key에 접근하기 위해서 리프노드까지 가야되는 단점이 있음

          중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있음

 

 

🔳 모든 node 를 확인해야 하는 B-Tree 와 달리
       B+Tree는 리프노드끼리 연결리스트(Linked list)의 형태를 띄어 선형 검색이 가능함

 

       > 작은 시간복잡도에 검색을 수행할 수 있음

 

 

 

B-Tree 가 아닌 B+Tree ?

 

인덱스 컬럼은 순차 검색 연산이 자주 발생할 수 있음

따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 됨

 

B+Tree의 검색 과정은 B-Tree와 동일하지만,

삽입과 삭제 과정은 약간의 차이가 있음

 

 

 

---

 

 

삽입

 

 

1. key의 수가 최대보다 적은 리프노드에 삽입하는 경우

 

 

기본적으로 B+Tree의 삽입과 삭제는 항상 leaf node에서 일어남

 

 

 

🔳 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우

 

       > 단순히 삽입해주면 됨

 

 

🔳 삽입 위치가 리프노드의 가장 앞 key 자리인 경우

 

       > 삽입 후 부모 key를 삽입된 key로 갱신하고,

          리프노드끼리 Linked list로 이어줘야 하므로 삽입된 key에 Linked list로 연결

 

 

 

2. key의 수가 최대인 leaf node에 삽입하는 경우

 

 

key의 수가 최대이므로 삽입하는 경우 분할을 해주어야 함

 

 

 

🔳 중간 node에서 분할이 일어나는 경우

    

       > 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정

 

 

 

 

 

🔳 리프노드에서 분할이 일어나는 경우는

 

       > 중간 key를 부모 node로 올려주는데 이때, 오른쪽 node에 중간 key를 붙여 분할한다.

          그리고 분할된 두 node를 Linked List로 연결

 

 

 

---

 

 

삭제

 

 

 

 

🔳 삭제할 key가 leaf node의 가장 앞에 있지 않은 경우

 

       > 단순히 삽입해주면 됨

 

 

 

 

 

🔳 삭제할 key가 leaf node의 가장 앞에 위치한 경우

 

       >  이 경우는 leaf node가 아닌 node에 key가 중복해서 존재함

           따라서 해당 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔주어야 함

 

 

 

---

 

Reference Path

 

[자료구조] 그림으로 알아보는 B+Tree

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

 

---