建于：20240116 00:00:00 Tuesday 3065字 11分
NOTE, DataStructure, B+ Tree, and Algorithm
CC BY 4.0（除特别声明或转载）
$B^+\ Tree$
Mary Search tree
 Binary search tree has one key to decide which of the two branches to take

Mary search tree needs M1 keys to decide which branch to take
 Mary search tree should be balanced in some way.
 We don’t want an Mary search tree to degenerate to a linked list, or even a binary search tree
 Thus, require that each node is at least half full!
Definition
 A B+ tree of order M
 Each internal node has at most M children (M1 keys)
 Each internal node, except the root, has between $\lceil \frac{M}{2} \rceil 1$ and $M1$ keys Each leaf has between $\lceil \frac{L}{2} \rceil $ and $L$ keys and corresponding data items
 A $B^+Tree$ of order M (M>3) is an Mary tree with the following properties:
 The data items are stored in leaves
 The root is either a leaf or has between two and M children
 The nonleaf nodes store up to M1 keys to guide the searching; key i represents the smallest key in subtree i+1
 All nonleaf nodes (except the root) have between $\lceil \frac{M}{2}\rceil$ and M children

All leaves are at the same depth and have between $\lceil \frac{L}{2}\rceil$ and L data items, for some L (usually L « M, but we will assume M=L in most examples)
 Keys in internal Nodes
 key i in an internal node is the smallest key in its i+1 subtree (i.e. right subtree of key i)
Insertion
 Suppose that we want to insert a key K and its associated record.
 Search for the key K using the search procedure. This will bring us to a leaf x
 Insert K into x
Insert Into Leaf
 If leaf x contains < L keys, then insert K into x (at the correct position in node x)
 If x is already full (i.e. containing L keys) then split x
 Cut x off from its parent
 Insert K into x, pretending x has space for K. Now x has L+1 keys.
 After inserting K, split x into 2 new leaves $x_L$ and $x_R$, with $x_L$ containing the $\lfloor \frac{L+1}{2} \rfloor$ smallest keys, and $x_R$ containing the remaining $\lceil\frac{L+1}{2}\rceil$ keys. Let J be the minimum key in $x_R$
 Make a copy of J to be the parent of $x_L$ and $x_R$, and insert the copy together with its child pointers into the old parent of x.
Insert Into Internal Node When leaf is Full and Internal Node is also Full
To insert a key K into a full internal node x:
 Cut x off from its parent
 Insert K and its left and right child pointers into x, pretending there is space. Now x has M keys (and M+1 pointers).
 Split x into 2 new internal nodes $x_L$ and $x_R$, with $x_L$ containing the $( \lceil \frac{M}{2} \rceil 1)$ smallest keys, and $x_R$ containing the $\lfloor \frac {M}{2} \rfloor$ largest keys. Note that the ${\lceil \frac{M}{2} \rceil}^{th}$ key J is not placed in $x_L$ or $x_R$ Make J the parent of xL and xR, and insert J together with its child pointers into the old parent of x.
Deletion
Situation I:
 The target is a key in some internal node (needs to be replaced, according to our convention)
Situation II:
 After deleting target from leaf x, x contains less than $\lfloor \frac{L}{2}\rfloor$ keys (needs to merge nodes)
Situation I Removal of a Key
After deleting from node x, we can access y directly and replace target by the new smallest key in x
Situation II Handling Leaves with Too Few Keys
Let u be the leaf that has $\lfloor \frac{L}{2}\rfloor$ keys (too few) Let v be a sibling of u with at least $\lceil \frac{L}{2}\rceil+1$ keys Let k be the key in the parent of u and v that separates the pointers to u and v There are two cases
Case I
Case 1: v contains $\lceil \frac{L}{2}\rceil+1$ or more keys and v is the right sibling of u Move the leftmost record from v to u
Case 2
v contains $\lceil \frac{L}{2}\rceil +1$ or more keys and v is the left sibling of u Move the rightmost record from v to u Then set the key in parent of u that separates u and v to be the new smallest key in u
BackLink
no link