二叉搜索树、B-树、B+树

二叉搜索树

二叉查找树，也称为二叉搜索树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉搜索树；

如果二叉查找树是平衡的则查找、插入的时间复杂度为O(logn)。如果二叉查找树完全不平衡则时间复杂度为O(n)。

中序遍历二叉搜索树可以获得关键字的递增序列

二叉搜索树的查找算法

在二叉查找树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的值，则查找成功；否则：
3. 若x小于b的根节点的值，则搜索左子树；否则：
4. 查找右子树。

二叉搜索树的节点插入算法

向一个二叉搜索树b中插入一个节点s的算法，过程为：

1. 若b是空树，则将s所指节点作为根节点插入，否则：
2. 若s->data等于b的根节点的值，则返回，否则：
3. 若s->data小于b的根节点的值，则把s所指节点插入到左子树中，否则：
4. 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

二叉搜索树的节点删除算法

1. 若待删除节点*p为叶子节点则直接删除即可
2. 若待删除节点*p只有左子树PL或右子树PR，则当*p是左子树（右子树）时直接令PL或PR成为其父节点*f的左子树（右子树）
3. 若待删除节点*p的左子树或右子树均不为空，
   • 其一是令*p的左子树为*f的左/右（依*p是*f的左子树还是右子树而定）子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；
   • 其二是令*p的直接前驱或直接后继替代*p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。
     

AVL树

AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和叶夫根尼·兰迪斯，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

AVL树是一种自平衡二叉搜索树，在AVL树中任一节点对应的两棵子树的最大高度差为1，查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)，增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

平衡因子：节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。

旋转操作：

• 右旋
  
• 左旋
  

需要平衡的四种情况：

B-树

参考文章

B-树就是B树，中间的横线并不是减号

为什么数据库索引使用B-树而不是二叉搜索树？
考虑磁盘IO的问题，数据库索引是存储在磁盘上的，当数据量比较大的时候，索引的大小可能有几个G甚至更多，当我们利用索引查询的时候只能逐一加载每一个磁盘页这里的磁盘页对应索引树的节点，最坏情况下磁盘IO次数等于索引树的高度，所以需要把原本“瘦高”的树结构变得“矮胖”，这就是B-树的特征之一。

B树是一种多路平衡查找树，每个节点最多可以包含k个孩子，k为B树的阶（k的选择取决于磁盘页大小）

一个m阶的B树具有如下几个特征：

1. 若根节点不是叶子节点则至少有两个子节点
2. 每个中间节点都包含 k-1 个元素和 k 个孩子，其中 ⌈m/2⌉ <= k <= m
3. 每个叶子节点都包含 k-1个元素，其中⌈m/2⌉ <= k <= m
4. 所有的叶子节点都位于同一层
5. 每个节点中的元素从小到大排列，节点当中k-1个元素刚好是k个孩子包含的元素的值域分划。

B-树主要应用于文件系统以及部分数据库索引，比如著名的非关系型数据库MongoDB，大部分关系型数据库比如Mysql则使用B+树作为索引。

B树的插入操作

参考博客
插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

1）根据要插入的key的值，找到叶子结点并插入。

2）判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。

3）以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。（ 当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。 ）

以5阶B树为例，介绍B树的插入操作，
在5阶B树中，结点最多有4个key，最少有2个key。

1. 在空树中插入39
   
   此时根结点就一个key，此时根结点也是叶子结点
2. 继续插入22、97、41
   
   根结点此时有4个key
3. 继续插入53
   
   插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。（当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。）
   
4. 依次插入13、21、40
   
   同样会造成分裂，结果如下图所示。
   
5. 依次插入30、27、 33 ；36、35、34； 24、29
   • 插入 30、27、 33
     
   • 插入 36、35、34；
     
     
   • 插入24、29
     
6. 插入26
   
   当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。
   
   进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。
   
   分裂后当前结点指向新的根，此时无需调整。
7. 最后再依次插入key为 17、28、31、32 的记录
   
   

B树的删除操作

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1. 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
2. 该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
3. 如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。
   否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
   有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

以5阶B树为例，介绍B树的删除操作
5阶B树中，结点最多有4个key,最少有2个key

1. 原始状态
   
2. 在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束
   
3. 在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。
   
   删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。
   
4. 在上述情况下接着删除32，结果如下图。
   
   当删除后，当前结点中只有一个key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。
   
   当前结点key的个数满足条件，故删除结束。
5. 上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。
   
   同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。
   
   同理，对于当前结点而言只能继续合并了，最后结果如下所示。
   
   合并后结点当前结点满足条件，删除结束。

B+树

参考文章
B+树是B-树的一种变体，有着比B-树更高的查询性能
一个m阶的B+树具有如下几个特征：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）的元素

在B-树中无论是中间节点还是叶子节点都有卫星数据（牵引元素所指向的数据记录），而在B+树中只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。

B+树的优点

• 单行查询
  在单元素查询的时候，B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。步骤与B-树类似，但是B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素，在数据量相同的情况下B+树比B-树更加“矮胖”查询IO的次数也更少。其次，B+树的查询必须最终查找到叶子节点，而B-树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点，因此B-树的查找性能不稳定（最好情况是根节点，最坏情况是叶子节点），而B+树的每次查找都是稳定的。

• 范围查询
  B-树的范围查询只能依靠繁琐的中序遍历，B+树的范围查询只需要在链表上做遍历即可。

总结：

1. 单一节点存储更多的元素，使得查询的IO次数更少。
2. 所有查询都要查找到叶子节点，查询性能稳定。
3. 所有叶子节点形成有序链表，便于范围查询。

红黑树