B-Tree

하나의 노드 안에 여러 개의 데이터가 꽉 채워져 있고, 가지도 여러 개로 뻗어나갈 수 있는 트리.

인덱스를 구성할 때 매우 잘 쓰이는 트리

그래서 옆으로 통통한 형태임(비만트리..)

 

양 옆으로 살이 쫙 늘어져 있으니 균형을 매우 잘잡음.

데이터가 편향되지 않기 때문에 항상 안정적으로 O(log n)임.

 

하드디스크 접근에 최적화 돼있음.

하드디스크에서 정보를 불러올 때 블록 단위로 가져오는데, B 트리가 노드 하나 당 다룰 수 있는 데이터가 많다 보니 블록 단위의 데이터를 잘 읽음.

 

그리고 항상 정렬된 상태를 유지함

 

데이터를 넣다가 노드가 꽉 차면 노드를 반으로 쪼개서 가운데 있던 데이터를 부모 노드로 올려보내 새 길을 개척함.

데이터 빼다가 텅 비면 옆 이웃 노드 데이터 빌리거나 아예 합쳐서 계속 비만 유지