一、 B树
1. 为什么需要B树
在大规模数据存储中，需要用到索引来加快数据查找，当数据非常之大的时候，采用二叉查找树、二叉查找平衡树、红黑树，内部元素结点个数有限。会导致树非常高，导致磁盘查找频繁，查询效率低下。因此需要降低树的深度，多叉树就是一个降低深度的想法。B树是一颗能够降低高度的树。那我们看看它是怎么降低高度，并且利用磁盘局部性原理，减少IO次数。
2. 什么是B树
B树也就是B-Tree，也叫B-树。可以用阶数m来定义一颗二叉树。
- 每个结点至多m颗子树
- 除非根结点是叶子结点，否则包含[2,m]颗子树
- 非根结点包含[m/2,m]个子树
- 叶子结点在同一层，不包含任何信息
- 有j个孩子的非叶节点包含j-1个关键码K，并且按照递增排序K[1]<K[2]...<K[J-1]
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
-
我画了一颗4阶的B树，符合上面的要求
image.png
3. B树高度
- 因为根至少有两个孩子，因此第2层至少有两个结点。
- 除根和叶子外，其它结点至少有┌m/2┐个孩子，
- 因此在第3层至少有2*┌m/2┐个结点，
- 在第4层至少有2(┌m/2┐^2)个结点，
= 在第 I 层至少有2(┌m/2┐^(l-2) )个结点，于是有： N+1 ≥ 2┌m/2┐I-2；
考虑第L层的结点个数为N+1，那么2(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个，即：I≤ log┌m/2┐((N+1)/2 )+2；
一棵含有N个总关键字数的m阶的B树的最大高度是多少?答曰：log_ceil（m/2）(N+1)/2 + 1
4. 二叉树操作
- 查找
BTreeNode *SearchBTree(BTree T，KeyType K，int *pos)
{ //在B-树T中查找关键字K，成功时返回找到的结点的地址及K在其中的位置*pos
//失败则返回NULL，且*pos无定义
int i；
T→key[0]=k; //设哨兵．下面用顺序查找key[1..keynum]
for(i=T->keynum；K<t->key[i];i--)； //从后向前找第1个小于等于K的关键字
if(i>0 && T->key[i]==1){ //查找成功，返回T及i
*pos=i；
return T；
} //结点内查找失败，但T->key[i]<K<T->key[i+1]，下一个查找的结点应为
//son[i]
if(!T->son[i]) //*T为叶子，在叶子中仍未找到K，则整个查找过程失败
return NULL；
//查找插入关键字的位置，则应令*pos=i，并返回T，见后面的插入操作
DiskRead(T->son[i])； //在磁盘上读人下一查找的树结点到内存中
return SearchBTree(T->Son[i]，k，pos)； //递归地继续查找于树T->son[i]
}
- 查找分为在内存中的内查找和在磁盘中的外查找。外查找跟树高度有关，o(h)，内查找复杂度o(nh),主要是一个结点中关键码的遍历。但由于外查找需要访问磁盘，因此外查找时间开销远大于外查找
- 插入操作
- 插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素，注意：如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。
- 删除操作
- 首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。
5. 使用场景
mongoDB数据库使用，单次查询平均快于Mysql
二、B+树
1. 特点
- 含有n颗子树的结点含有n个关键码
- 叶子结点包含所有关键信息，非叶子结点作为索引，
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字
- 含有[m/2,m]颗子树
-
根结点含有[2,m]颗子树
image.png
2. 与B树相比更适合于文件索引和数据库索引
- 查询效率稳定，每次查询都要访问到叶子结点，因此查询速度取决于树的高度
- 叶子结点形成链表，便于区间查找
- 磁盘代价更低：B+树的非叶结点只存放索引，不含有关键信息，所以一个结点的存储数据更多，减少磁盘的访问
3. 使用场景
Mysql数据库索引
