一、B-树

1. B-树是一种多路搜寻树（并不一定是二叉的）

1970年，R.Bayer和E.mccreight提出了一种实用于外查找的树，它是一种均衡的多叉树，称为B树（或B-树、B_树）。

2. 一棵m阶B树(balanced tree of order m)是一棵均衡的m路搜寻树。它或者是空树，或者是满足下列性质的树：

  1. 根结点至多有两个子女；
  2. 每个非根节点所蕴含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
  3. 除根结点以外的所有结点（不包含叶子结点）的度数正好是关键字总数加1，故外部子树个数 k 满足：┌m/2┐ <= k <= m ；
  4. 所有的叶子结点都位于同一层。

二、特点：

是一种多路搜寻树（并不是二叉的）：

  1. 定义任意非叶子结点最多只有M个儿子；且M>2；
  2. 根结点的儿子数为[2, M]；
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  4. 每个结点寄存至多M/2-1（取上整）和至少M-1个关键字；（至多2个关键字）
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  8. 所有叶子结点位于同一层；

如：（M=3）

B-树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果

命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为

空，或曾经是叶子结点；

三、B-树的个性：

  1. 关键字汇合散布在整颗树中；
  2. 任何一个关键字呈现且只呈现在一个结点中；
  3. 搜寻有可能在非叶子结点完结；
  4. 其搜寻性能等价于在关键字选集内做一次二分查找；
  5. 主动档次管制；

四、B+树

B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一棵B+树蕴含根节点、外部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个蕴含两个或两个以上孩子节点的节点。

五、用处：

B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在应用B+树作为元数据索引。B+ 树的特点是可能保持数据稳固有序，其插入与批改领有较稳固的对数工夫复杂度。B+ 树元素自底向上插入。

六、B+树的定义

1. B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差别在于：

  1. 有n棵子树的结点中含有n个关键字，每个关键字不保留数据，只用来索引，所有数据都保留在叶子节点。
  2. 所有的叶子结点中蕴含了全副关键字的信息，及指向含这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大程序链接。
  3. 所有的非终端结点能够看成是索引局部，结点中仅含其子树（根结点）中的最大（或最小）关键字。
    通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

2. B+树是B-树的变体，也是一种多路搜寻树：

  1. 其定义根本与B-树同，除了：
  2. 非叶子结点的子树指针与关键字个数雷同；
  3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
  4. 为所有叶子结点减少一个链指针；
  5. 所有关键字都在叶子结点呈现；

如：（M=3）

B+的搜寻与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树能够在

非叶子结点命中），其性能也等价于在关键字选集做一次二分查找；

七、B+的个性：

  1. 所有关键字都呈现在叶子结点的链表中（浓密索引），且链表中的关键字恰好是有序的；
  2. 不可能在非叶子结点命中；
  3. 非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层；
  4. 更适宜文件索引零碎；

八、B*树：

1. 是B+树的变体，在B+树的非根和非叶子结点再减少指向兄弟的指针；

2. B*树定义了非叶子结点关键字个数至多为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的决裂：当一个结点满时，调配一个新的结点，并将原结点中1/2的数据复制到新结点，最初在父结点中减少新结点的指针；B+树的决裂只影响原结点和父结点，而不会影响兄弟结点，所以它不须要指向兄弟的指针；

B_树的决裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字（因为兄弟结点的关键字范畴扭转了）；如果兄弟也满了，则在原结点与兄弟结点之间减少新结点，并各复制1/3的数据到新结点，最初在父结点减少新结点的指针；所以，B_树调配新结点的概率比B+树要低，空间使用率更高；

九、小结：

1. B-树：

多路搜寻树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范畴的子结点；所有关键字在整颗树中呈现，且只呈现一次，非叶子结点能够命中；

2. B+树：

在B-树根底上，为叶子结点减少链表指针，所有关键字都在叶子结点中呈现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命；

3. B*树：

在B+树根底上，为非叶子结点也减少链表指针，将结点的最低利用率从1/2进步到2/3；

十、B-树，B+树与B*树的优缺点比拟

首先留神：B树就是B-树，"-"是个连字符号，不是减号。

B-树是一种均衡的多路查找(又称排序)树，在文件系统中有所利用。次要用作文件的索引。其中的B就示意均衡(Balance)

B+树有一个最大的益处，不便扫库，B树必须用中序遍历的办法按序扫库，而B+树间接从叶子结点挨个扫一遍就完了。

B+树反对range-query(区间查问)十分不便，而B树不反对。这是数据库选用B+树的最次要起因。

比方要查 5-10之间的，B+树一把到5这个标记，再一把到10，而后串起来就行了，B树就十分麻烦。B树的益处，就是胜利查问特地无利，因为树的高度总体要比B+树矮。不胜利的状况下，B树也比B+树稍稍占一点点便宜。

B树的劣势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会胜利并完结查问，而B+树因为非叶节点只是索引局部，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是持续向下直到叶子节点。因而在B+树中，无论查找胜利与否，都是走了一条从根到叶子节点的门路。

有很多基于频率的搜寻是选用B树，越频繁query的结点越往根上走，前提是须要对query做统计，而且要对key做一些变动。
另外B树也好B+树也好，根或者下面几层因为被重复query，所以这几块根本都在内存中，不会呈现读磁盘IO，个别已启动的时候，就会被动换入内存。 mysql底层存储是用B+树实现的，因为内存中B+树是没有劣势的，然而一到磁盘，B+树的威力就进去了。

B*树

是B+树的变体，在B+树的非根和非叶子结点再减少指向兄弟的指针；B_树定义了非叶子结点关键字个数至多为(2/3)_M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的决裂：当一个结点满时，调配一个新的结点，并将原结点中1/2的数据复制到新结点，最初在父结点中减少新结点的指针；B+树的决裂只影响原结点和父结点，而不会影响兄弟结点，所以它不须要指向兄弟的指针；

B*树的决裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字（因为兄弟结点的关键字范畴扭转了）；如果兄弟也满了，则在原结点与兄弟结点之间减少新结点，并各复制1/3的数据到新结点，最初在父结点减少新结点的指针； 所以，B*树调配新结点的概率比B+树要低，空间使用率更高；