CSE201W2b_B+Tree

$B^+$树（$B^+$-tree）索引结构是在数据插入和删除下仍能保持其执行效率的几种使用最广泛的索引结构之一。B+树采用平衡树（balanced tree）结构

B+树的基本要求

B+树结点最多包含$n - 1$个搜索码值$K_1, K_2, ..., K_{n-1}$，以及$n$个指针$P_1, P_2, ..., P_n$,每个结点的搜索码值排序存放。
根结点（root）必须至少有两个子结点
在每个非叶结点（nonleaf node）至少容纳$\lceil n/2 \rceil$个指针
在每个叶结点（leaf node）至少容纳$\lceil (n-1)/2 \rceil$个搜索值
一个B+树的高度不得超过$\lceil log_{\lceil n/2 \rceil} (K) \rceil$

B+树的查询

B+树的更新

• Splitting a leaf node：

1. 将$n$个搜索码值和指针（包括插入的）放入一个可以存放的区域$M$，将前$\lceil n/2 \rceil$放入原先的结点，将剩余的放入一个新结点
2. 将新结点视为$p$，将该结点内最小的搜索码值视为$k$，将$(k,p)$放入父结点
3. 如果父结点也满了，就顺级分离。

• Splitting a non-leaf node:
  当插入搜索码值和指针到一个已经没有位置的非叶结点$N$时

1. 将$N$放到一个可以储存$n$个搜索码值和$n+1$个指针的区域$M$
2. 将要插入的$(k,p)$按照排列插入$M$中
3. 将$P_1, K_1, ..., K_{\lceil n/2 \rceil - 1}, P_{\lceil n/2 \rceil}$从$M$抄写到原来的$N$中
4. 将$P_{\lceil n/2 \rceil+1}, K_{\lceil n/2 \rceil+1}, ..., K_n, P_{n+1}$从$M$抄写到新的非叶结点$N’$
5. 将($K_{\lceil n/2 \rceil}$, $N’$)写到父结点中。

分离结点的最差情况是整体高度+1

B+树的删除

• 删除后，如果该结点的搜索码值过于少，并且该结点可以和它的兄弟结点相结合成一个结点，我们使用merge siblings:

1. 将两个结点的所有搜索值码放入一个搜索值码中，并删除另一个结点。
2. 如果它是一个非叶结点，将两个结点中的父节点拷贝到结合的结点中
3. 将（$K_{i-1}, P_i$）从父节点中删除，$P_i$是指向原先存在结点的指针，重复上述过程

• 删除后，如果该结点的搜索码值过于少，但是又不能和它的兄弟结点相结合成为一个结点，我们使用redistribute pointers:

1. 重新分配它和它兄弟结点的指针使这两个结点都满足最少搜索码值的要求，更新父节点中的搜索码值
2. 如果是叶结点：将一个适合的搜索码值从它的兄弟结点中移到该结点里，将父节点中的旧搜索码值替换为合适的搜索码值
3. 如果是非叶结点：将父节点中的旧搜索码放入不满的结点中，将一个合适的搜索码值从兄弟结点中移到父节点中。
   
   
   

level below root?