简介

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。（相对于二叉，B树每个内结点有多个分支，即多叉）
B树又可以写成B-树

 

B-Tree

特性

M阶BTree几个特性（m>=2）
1、节点最多含有m个子树（指针），m-1个关键字
2、除根节点和叶子节点外，其他每个结点至少有ceil(m/2)个子节点，ceil为向上取整
3、若根节点不是叶子节点，则至少有两颗子树

 

3阶B-tree

P1 P2 P3为指针  17 15为关键字

 

B-树的搜索

从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点

B-树的插入

生成从空树开始，逐个插入关键字。但是由于B_树节点关键字必须大于等于[ceil(m/2)-1],（其中ceil(x)是一个取上限的函数）所以每次插入一个关键字；首先在最底层（叶子节点那一层）的某个非终端节点中添加一个“关键字”，该结点的关键字不超过m-1,则插入完成；否则要产生结点的“分裂”，将一半数量的关键字分裂到新的其相邻右结点中，中间关键字上移到父结点中。

B-树的删除

首先查找B树中需删除的关键字,如果该关键字在B树中存在，则将该关键字在其结点中进行删除，如果删除该关键字后，首先判断其结点是否有左右孩子结点，如果有，则上移孩子结点中的某相近关键字到父节点中，然后是判断移动之后的情况；如果没有，直接删除后，判断删除之后的情况。

 

B+Tree

特性

1、每个节点最多有m个子节点
2、除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽就向上取整
3、根节点要么为空要么独根，否则至少有两个子节点
4、存在k个子节点的节点必有k个关键字
5、叶节点高度一致

 

3阶B+tree

B+Tree和BTree的区别在于

B+Tree非叶子结点的子树指针与关键字个数相同，BTree关键字比指针小1
B+Tree非叶子结点的子树指针p1->k1,k2 | p2->k2,k3 | p3->k3,∞，BTree指针p1->-∞,k1 | p2->k1,k2 | p3->k2,∞
B+Tree所有的数据存储在叶子节点，非叶子节点存索引，BTree数据存在所有节点
B+Tree叶子节点直接存在双向链表，可以双向查找数据

 

二叉查找树\红黑树\BTree\B+Tree总结

二叉查找树：二叉搜索树：优点查找快，但是某种情况下会退化成链表，所有高效查找数的基础

红黑树：内存查找高效树，不适合大数据和磁盘存储，适合底层系统做内存运算

BTree可以认为是B+Treed过渡

B+Tree最适合大数据的磁盘索引，经典的mysql索引，所有数据都存在叶子节点，增加系统的稳定性以及遍历查找效率