[목차]

Dynamic Multi-level Indexes

• 이전까지 배운 index structures 특징
  • Tuple Insertions and Deletions
    • need Overflow Pages to deal with insertions
  • insert/delete가 없이 조회만 하는 것은 okay
  • insert/delete가 자주 일어나는 데이터베이스에서는 좋지 않음
• 따라서, 대부분의 멀티레벨 인덱스는 B-tree or B+tree 사용
  • 각 노드는 disk block에 해당함
  • insert/delete 시, rebalancing operations !
    • 각 node는 half-full 이상을 유지

B-Tree

• Ki는 search key value

• Pi는 Pointer to children (non-leaf nodes) or Pointer to records or bucket of records (leaf nodes)

• 노드 내의 key는 항상 정렬

• https://www.cs.usfca.edu/~galles/visualization/BTree.html

• 각 node는 data pointer를 가지고 있음

• Balanced

  • root에서 leaf까지 모든 path의 depth는 동일함
  • must contain q/2 entries (root 제외)
    • q는 order of the tree

• Searching a Record in B-tree

  • Logarithmic
    • logB(n), B = order of the B-tree (number of entries per block)
    • 보통, B = 100
  • relation이 1,000,000,000 entries를 가지고 있을 때, 4~5 random accesses만 하면 됨
  • top-levels은 메모리에 저장되어 있어서,
    • 사실, 1~2 번의 access만 해도 됨

Summary of B-tree

• Searching
  • logB(n), B = number of entries per block, n = total number of entries
• Insertion (split)
  • insert할 leaf node 찾기
  • If full, split the node, and adjust index accordingly
  • Similar cost as searching