[CMU 15-445 Intro to DB Sys] Lec08 B+Tree Index

B+Tree

• self-balancing, ordered tree data structure
• search, sequential access, insertion, deletions을 $O(\log n)$에 수행
• $M$-way search tree($M$: maximum number of children a node can have)
  • perfectly balanced(every leaf node is at the same depth)
  • every node other than the root is at least half-full($M/2 -1 \leq # keys \leq M - 1$)
  • every inner node with $k$ keys has $k+1$ non null children
• B-Tree와의 차이점은 B+Tree에서는 value가 Leaf node에만 저장된다는 점임. B+Tree의 inner node는 "guide post" 역할을 함.*

  Nodes

• 각 node는 key/value pair의 array로 구성되며, 대체로 sorted key order로 유지됨. sibling node 간에는 오갈 수 있는 포인터가 있음.
  • key는 index가 기반하는 attribute로부터 옴.
  • value 값은 inner node냐 leaf node냐에 따라 다름. inner node에서는 value가 다른 node로 가는 포인터가 있으며, leaf node에서는 데이터 값을 가리키는 포인터(Record ID) 또는 tuple data가 있음.
    • 여기서 tuple data를 직접 담는 방법은 오직 primary key에만 적용해야 하며, secondary key 이후로는 record ID만 넣어야 함(tuple data를 다 넣을 경우 중복해서 넣는 것임)
• NULL key는 첫번째 또는 마지막 leaf node에 모아둠.

  Insert

• find correct leaf node $L$
• add new entry into $L$ in sorted order
  • if $L$ has enough space, operation is done
  • otherwise, split $L$ into two nodes; redistribute entries evenly and copy up the middle key. insert an entry point to $L_2$ into the parent of $L$
• inner node의 경우, redistribute entries evenly, but push up the middle key

Delete

• find the correct leaf node $L$
• remove the entry
  • if $L$ is at least half full, operation is done
  • otherwise, borrow from the sibling
  • if redistribution fails, merge $L$ and the sibling
  • if merge occurred, must delete the entry in the parent pointing to $L$

Selection Conditions

• B+Tree index에서는 entire search key를 갖고 있을 필요가 없이 그 일부만으로도 찾아갈 수 있다. 반면 hash index에서는 모든 attribute를 가지고 있어야 한다.
• 하지만 모든 DBMS가 이를 지원하는 것은 아니다.

Duplicate Keys

• 두 가지 접근법이 있다.
  • 1) key에다가 tuple의 Record ID를 append하게 되면 key가 모두 Unique해진다(위에서 보았듯 B+Tree에서는 key의 일부만으로 search할 수 있으므로 문제 없다)
  • 2) leaf node가 overflow node를 갖게 하여 duplicate key를 보관하게 함. 그러나 이 방식은 관리하기 더 복잡함.

Clustered Index

• clustered index를 사용하는 경우에는 page들이 이미 index 순서에 따라 정렬되어 있기 때문에 왼쪽에서 오른쪽으로 scan해 나가면 속도가 빠르다.
• non-clustered index의 경우 왼쪽에서 오른쪽으로 scan하면서 여러 페이지를 redundant하게 읽어들여서 비효율적으로 될 수 있다.
  • 따라서 이를 효율적으로 하기 위해서 우선 leaf node를 보면서 어떤 tuple들이 필요한지를 파악한 뒤, 이를 Page id순으로 정렬하여 필요한 페이지를 한번씩만 읽어 들인다.

B+Tree Design Choices

Node Size

• storage device가 느릴 수록 큰 node size를 사용한다.

  Merge Threshold

• 절반보다 작아졌다고 바로 Merge하지 않고, 작은 채로 두었다가 나중에 Rebuild한다.
• 왜냐하면 merge하는 과정에서 많은 수의 delete과 insert가 발생할 수 있기 때문이다.

  Variable-Length Keys

• Pointers: key를 직접 저장하는 대신 key를 향한 포인터를 저장한다. 비효율성으로 인해 embedded device 정도에서나 사용한다(register, cache가 작기 때문에 space saving이 의미가 있음)
• variable length node
• padding: 최대 Key의 크기에 맞게 패딩을 붙여주는 것인데, 메모리 낭비가 심하여 사용되지 않음
• key map/indirection: 별도 dictionary에 key-value pair를 만들고, 이 dictionary에 대한 Index로 대체하는 방식이다. 대부분 이 방식을 사용함.

  Intra-Node Search

• Linear: leaf node 내에서 linear scan으로 우리가 원하는 key를 찾음. SIMD("심디", single instruction multiple data)를 통해 vectorize할 수 있음.
• Binary: 중간에서 시작해서 좌/우로 쪼개가면서 보는 방식으로, 대부분 이를 사용
• Interpolation: key의 알려진 분포를 이용하여 위치를 근사함.

Optimizations

Pointer Swizzling

• node가 서로 다른 node로 갈 때 page id를 사용하는데, 만약에 page가 buffer pool 내에 이미 Pin된 상태라면 굳이 page table을 찾아볼 필요 없이, Raw pointer를 이용할 수 있다.

  Bulk Insert

• 이미 존재하는 table로부터 b+Tree를 만들기 위해서는 key를 sort한 뒤에 bottom up방식으로 만들어 올라가는 것임.

  Prefix compression

• 같은 leaf node 내에서 key들은 정렬되어 있어서, 같은 Prefix를 가질 것으로 보임. 그래서 이를 중복해서 저장하는 것이 아니라 node 앞부분에 prefix만을 분리해서 저장하고 각 key들에서는 unique section만을 남겨둘 수 있음.

  Deduplication

• non-unique key의 경우 Key를 여러번 쓰지 않고 생략하여 한 번만 쓰고, 이에 속하는 value들을 나열하여 쓸 수 있음.

  Suffix Truncation

• inner node의 key들은 가이드하는 데만 사용되기 때문에 꼭 필요한 앞부분의 minimum prefix만을 남겨둠.

Write-Optimized B+Tree

• 결국 split/merge node하는 작업이 expensive해지는데, 이러한 Update를 남겨두었다가 나중에 batch로 하는 방법을 고안한다.
• root node, inner node상에 Mod Log를 유지한다. update가 생기면 이를 root node의 Mod Log 상에 저장해 둔다. 이후 무언가를 find해야 할 때 mod log를 보고 변화된 게 있다면 바로 결과를 알 수 있다.
• 시간이 흐름에 따라 buffer가 가득차게 되는데, 이를 아래 node로 cascade down시켜준다.