데이타베이스 Multilevel Indexes

Multilevel Indexes

• 탐색시 탐색할 공간을 줄이기 위해 사용한다.
• 탐색에 사용되는 시간 또한 자연스럽게 줄어든다.

Level of multilevel index

1LV - Index of file

• Base Level

2LV - Primary Index to first level

• Intermediate

3LV - Primary Index to second level

• Highest

---

Dynamic Multilevel Indexes

• 위 방식은 index 제거 및 추가에 문제가 있다.
• 모든 레벨이 물리적으로 정돈되어 있어 수정이 어렵기 때문이다.
• 이런 불편함을 해결하기 위해
  • 각각의 index block에 새로운 엔트리 추가를 위한 공간을 두거나
  • 적절한 추가/삭제 알고리즘을 사용한다.
• 그것이 바로 트리에 기반한 Dynamic Multilevel Index 방식이다.

---

Search Tree

( EX. Binary Search Tree )

• 레코드의 검색을 돕기 위해 사용된다.
• X는 레코드 필드의 값이다.

---

B+ Tree

• $\log_{p}{N}$ 안에 삽입, 삭제가 일어난다.
• 높이의 균형이 유지된다.
• 최소 Leaf node의 50퍼센트에 데이터가 존재한다.
• 각 노드는 d <= n <= 2d 개의 entry를 가진다.
  • d : order of the tree ( 한개의 Leaf Node 혹은 Internal Node가 가지는 최대 값의 갯수를 정한다. )
• Leaf node끼리 연결되어 있어, Range-search 를 지원한다.

Internal node

• 검색에 관여한다.
• 데이터는 저장되지 않는다.
• n개의 엔트리 포함시 자식은 n+1 개를 가진다.
• left <= n < right 사이의 값을 Leaf node에 가진다.

Leaf node

• 데이터 포인터가 저장된다.
• 검색되는 필드의 모든 값들의 엔트리를 가진다.
  • key 값일 경우 레코드를 가리키는 값
  • key 값이 아닐경우 해당 레코드들을 가리키는 블럭의 포인터를 가진다, 결과가 여러개일수 있다는 이야기.

예시 : order 이 2인 B+ Tree

• root에서 검색이 시작된다.
• 5를 검색하려면 13보다 작기에 13 왼쪽의 자식 노드에 찾아간다.
• 15를 검색하려면 13과 17 사이의 자식노드를 찾아간다.
  • 값이 없을수 있다.

B+ 트리에 값을 삽입하기

• 올바른 leaf L을 찾는다.
• L에 엔트리를 집어 넣는다.
  • L에 공간이 충분하다면 괜찮지만, 그렇지 않다면 L을 분할한다.

공간이 있는 경우의 추가 예시

공간이 없는 경우의 추가 예시

• 꽉 찬 노드의 절반을 새로운 노드에 옮긴다.

• 부모 노드에 추가된 노드를 업데이트 한다.

• 그 뒤 값이 추가된다.
• 값이 더 추가되면 Depth/Height 도 늘어날수 있다.

추가 예시

• 위 경우에 8을 추가한다.
  
• 먼저 아래가 쪼개진다.
  
• 그 다음에 위가 쪼개진다.
• Internal Node가 쪼개질때엔 중간에 있는 값이 Parent로 올라간다.

추가 방식

• Height 를 변경하지 않고, Leaf node 들 전체에 재분배할수도 있다.

B+ 트리에 값을 삭제하기

• 엔트리를 삭제한다.
• 최소한 절반이 차있으면 넘긴다.
• 만약 d-1 개의 엔트리가 있을시, 자매 값으로 부터 빌려온다.
• 빌려오기가 실패할 경우 그냥 자매와 합친다.
• 합치기가 진행되면 부모 Internal Entry의 값도 삭제된다.
• 루트까지 진행되어 높이가 줄어들수도 있다.

• 19는 그냥 제거되나 20을 제거 하면 Leaf Node에 22 하나밖에 남지 않아 오른쪽 Sibling에서 24를 가져왔다.
• 그에 맞게 Internal Node의 값이 수정된다.
  • 새롭게 바뀐 첫번째 값으로 그대로 올라간다.

• 24를 제거할 경우 오른쪽에서 가져와도 오른쪽이 1개만 값이 가져지기 때문에 그냥 오른쪽을 합친다.
• 22, 27, 29를 가지는 Leaf Node가 생기고 이를 위에 적용시 또 바로 위의 Internal Node가 1개가 된다.
• 왼쪽과 루트와 합쳐 높이가 줄어든다.
• 두개를 합칠때 Leaf Node를 합칠경우 합치는 사이의 Internal Node의 엔트리는 없어진다 ( 27 )

---

B 트리

• Internal node에 바로 데이터를 저장할수 있다.
• 성능이 항상 일정하지 않다.

실전 B+ 트리

• 대부분의 Order : 100
  • 평균적으로 노드의 67%정도가 사용중이다.
  • Internal node의 fanout ( 갈래 ) - 133
• 높이 4일때 312,900,700 개의 레코드 저장 가능
  • 133 ^ 4
• 높이 3일때 2,352,637 개의 레코드 저장 가능
  • 133 ^ 3