📌 B Tree란?

좌우 균형을 맞추어 트리의 검색, 삽입, 삭제 시 시간 복잡도를 개선한 자료구조입니다. 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree입니다.

B Tree 규칙

• 노드의 데이터 수가 N이면, 자식 수는 N+1
• 각 노드의 데이터는 정렬된 상태이어야 함
• 루트 노드는 적어도 2개 이상의 자식을 가져야 함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어야 함 (M=노드 내 최대 데이터 수)
• 외부(단말) 노드로 가는 경로의 길이는 모두 같다
• 입력 자료는 중복될 수 없음

B Tree 삽입

• 새로운 데이터 key를 삽입할 단말(리프) 노드 찾기
• 찾은 노드의 공간에 여유가 있으면 키를 삽입하고 끝낸다
• 찾은 노드의 공간에 여유가 없으면, 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘긴다
• 형제 노드의 공간에도 여유가 없으면 노드를 두개로 분리한다. 분리 작업은 부모 노드에서의 삽입 작업을 포함한다.

B Tree 삭제

• 삭제하고자 하는 데이터 key(x)를 갖고 있는 노드를 찾는다
• 찾은 노드가 단말(리프) 노드가 아니면, x의 직후원소인 y를 가진 리프노드를 찾아와 x와 y를 맞바꾼다
• 리프 노드에서 x를 제거한다
• x 제거 후 노드에 언더플로우가 생기면 적절히 해소한다

📌 B+ Tree란?

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있습니다.
(기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조) B-Tree의 변형 구조로, index 부분과 Leaf 노드로 구성된 순차 데이터 부분으로 이루어집니다. 인덱스 부분의 key 값은 Leaf에 있는 key 값을 직접 찾아가는데 사용합니다.

B+ Tree 특징

• 데이터의 빠른 접근을 위한 인덱스 역할만 하는 노드가 추가로 있음
• 모든 key, data가 리프노드에 모여있음
• 모든 리프노드가 연결리스트 형태를 띄고 있으므로 재검사 시 리프노드에서 선형 검색으로 시간 복잡도 감소
• 리프노드의 부모 key는 리프 노드의 첫 번째 key보다 작거나 같음
• Key 값에 대한 HDD 액세스 주소 없음 → 블럭 사이즈 더 많이 이용 가능
• Leaf 노드끼리 연결 리스트로 연결 → 범위 탐색에 유리
• 최상의 케이스의 경우 루트에서 끝날 수 있는 B-Tree와 달리, 무조건 Leaf까지 가봐야 함

📌 B-Tree & B+ Tree

활용

• 데이터베이스 (B+ Tree)
• 파일 시스템
• 다량의 데이터를 처리할 때

정리

• B tree는 각 노드에 데이터가 저장됨
• B+tree는 index 노드와 leaf 노드로 분리되어 저장됨 (또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)
• B-tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있음
• B+tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재
• B+tree는 add와 delete가 모두 leaf 노드에서만 이루어짐

참고

• https://gyoogle.dev/blog/computer-science/data-structure/B%20Tree%20&%20B+%20Tree.html
• https://thinking-developer.tistory.com/73

피드백 및 개선점은 댓글을 통해 알려주세요😊