[자료구조] B-트리 B+트리 B*트리

1. 다원 탐색 트리(Multiway search tree)

• m-원 탐색 트리 (m-way search tree)라고도 한다.
• 다원 탐색 트리는 한 노드 안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있다.
• 이진 탐색 트리는 m=2 인 다원 탐색 트리

 

2. B 트리

Balanced Tree. 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 균등한 응답속도를 유지하기 위해서 리프 레벨에서 좌우 균형을 유지한다.

• 모든 노드는 최대 m개의 자식들을 가진다.
• 루트 노드와 리프 노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다.
• 루트노드는 최소 2개 이상의 자식을 가진다.
• k개의 자식을 가진 리프 노드가 아닌 노드는 k-1개의 키를 가진다. = 키가 n개 있으면 이 노드의 자식은 n+1개
• 모든 리프노드들은 같은 높이에 있어야 한다.
• 모든 노드들은 키와 자식 노드에 대한 포인터로 이루어져 있다.
• 노드의 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산이 필요하다(재분배, 합병)
• 순차 검색 느림
• 시간 복잡도 : O(logN)

 

2-1. B 트리 삽입 연산

 

 

2-2.  B 트리 삭제 연산

 

 

---

3. B+ 트리

순차검색 향상을 위해 Index Set과 Data Set을 구분한다. 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리 자료구조의 일종이다. 이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소 범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다. 리프 노드 간에 연결 리스트가 구성되어 순차 탐색의 효율이 높다. 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.

• 블록 인덱싱을 위해 B+트리 타입을 이용하는 파일 시스템 : ReiserFS filesystem (Unix and Linux), XFS filesystem (IRIX, Linux), JFS2 filesystem (AIX, OS/2, Linux), NTFS filesystem (Microsoft Windows)

 

3-1. B +트리 삽입 연산

 

3-2. B +트리 삭제 연산

 

---

4. B* 트리

삽입 시 빈번한 노드 분할에 따른 연산을 감소시킨 트리. B-Tree의 생성되는 노드의 수를 줄이기 위해 B-Tree의 변형으로 B* 트리가 나오게 되었다. B-Tree는 특성을 유지하기 위해 삽입과정에서의 분열과 삭제 과정에서의 합병 등의 보조 연산이 필요하다. B* Tree에서는 이런 보조 연산을 가급적 지연시켜 회수를 감소시키려 했다.

• 노드의 약 2/3이상이 채워지는 B트리
• 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김. 하나의 노드가 오버플로우 되면 여유 공간이 있는 이웃 노드에 재분배 과정을 거쳐 삽입된다.
• 삽입/ 삭제 시 발생하는 노드 분리를 줄이려고 고안됨
• 데이터가 기본적으로 정렬되어 저장됨
• Max/Min의 효율적 처리 가능

 

---

참조
https://www.cs.usfca.edu/~galles/visualization/BTree.html
https://www.youtube.com/watch?v=Y11hGrKbilU
https://itwiki.kr/w/B*_%ED%8A%B8%EB%A6%AC
https://itwiki.kr/w/B_%ED%8A%B8%EB%A6%AC