데이터베이스 저장기법_트리, B - Tree, B+ - Tree, B* - Tree

▣ 데이터베이스 저장기법_B - Tree, B+ - Tree, B* - Tree

인덱스를 조직하는 구조로 가장 많이 사용하는 것이 B-트리(B-tree)임

데이터를 효율적으로 검색/갱신하기 위해 탐색트리에 몇개의 제약을 붙이고 확장한 것

1) 트리는 공백이거나 높이가 1 이상인 m원 탐색 트리임

2) Root와 Leaf node를 제외한 각 노드는 최대 m개, 최소 m/2개의 서브트리를 가져야 함

3) 노드에는 최대 M-1개 부터 [M/2]-1개의 키가 포함될 수 있음

4) 노드의 키가 X개 라면 자식의 수는 X+1개 입니다.

5) Root node는 그 자체가 Leaf가 아닌 이상 적어도 2개의 서브트리를 가져야 함

6) 모든 Leaf node는 같은 레벨에 있어야 함

 

B-Tree는 삽입, 삭제 시 균형 유지를 위해 복잡한 재분배, 병합 연산등이 발생하고,

특히 삽입시 빈번한 Split발생과 순차접근시 중위순회 탐색으로 인한 비효율이 발생함

구분	B-Tree	B+-Tree	B*-Tree
접근성	순차 접근이 어렵고 탐색은 중위 순회 운행 탐색을 하면서 원하는 키값의 레코드 위치 파악 루트 노드를 제외한 모든 노드는 1/2이상 채워져야 함	순차접근이 용이 레코드 위치는 Leaf 노드에서만 파악 가능	노드 split은 모든 형제 노드의 재분배 이후 발생 루트 노드를 제외한 모든 노드는 2/3이상 채워져야함
중복성	탐색 키의 중복성을 제거함	Index Set와 Sequence Set에 중복성이 존재	탐색 키의 중복성을 제거함
복잡성	Leaf가 아닌 노드 사이즈가 더 크고 인덱스에 대한 저장공간 관리가 복잡	모든 노드의 크기가 같고 삭제될 노드가 항상 Leaf 노드에 존재	삽입시 split 현상의 최소화
특징	하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 m원 탐색 트리 자료구조	모든 키 값들이 잎 노드에 정렬되어있는 트리 구조 루트와 잎 노드를 제외한 트리의 노드는 최소 ⌈m/2⌉개의 서브트리	공집합이거나 높이가 1 이상인 m원 탐색 트리

 

 

---

2019년 72번

정답 : 4번

1) B-트리는 루트 노드를 제외한 모든 노드는 1/2이상 채워져야 함 (루트 노드 제외로 1번 틀림)

2) B+-트리는 루트 노드를 제외한 모든 노드는 1/2이상 채워져야 함 (루트 노드 제외로 2번 틀림)

3) B+-트리는 내부 노드의 키 값이 단말노드에 중복하여 나타남 ( B+-트리 특징 3번 틀림)

4) 맞음

 

B+-Tree 구조는 키 값의 경로를 제공하는 Index Set와 키 값과 데이터를 포함하는 단말(Leaf) 노드로만 오름차순 정렬되어 있는 Sequence Set으로 구성되어 있음 / Index Set의 키 값들이 Sequence Set에도 중복해서 존재

 

---

2021년 58번

정답 : 4번

B-Tree 삽입 연산

- 리프노드 여유 공간이 있는 경우 : 단순히 순서에 맞게 새로운 키 값을 삽입

- 리프노드 여유 공간이 없는 경우(overflow 발생) : split 발생

: 해당 리프 노드에 새로운 키 값을 삽입 시 그 중간 키 값을 중심으로

왼편 작은 키들은 해당 노드에 그대로 남겨 두고,

오른편 큰 키들은 분할(split)된 새로운 노드에 저장함

중간 키 값은 분할된 노드의 부모 노드로 올려 보내 삽입함

만일 부모 노드로 올라간 중간 키 값을 삽입할 때

또 다시 오버플로 발생하면 똑같은 과정의 분할 작업을 다시 반복 수행함

 

키 값 30일 삽입하기 위하여 27.29와 33, 34 사이에 30을 삽입하므로 오버플로가 발생

중간키 값인 30을 기준으로 왼편 27.29는 해당 노드에 그대로 남겨 두고,

오른편 33, 34는 분할된 새로운 노드에 저장됨

중간키 값인 30은 부모 노드에 삽입되지만, 다시 오버플로가 발생함

30이 삽입된 부모 노드에서 중간 키 값인 26을 기준으로 마찬가지로 분할되고

중간키 값인 26은 새롭게 생성된 부모 노드로 올라감

 

따라서, 보기 1), 2), 3)번은 맞고 4)번은 병합이 발생하지 않으므로 틀림

일반적으로 B-Tree 삽입시 병합연산이 발생하지 않으므로 직관적으로 선택가능