数据库索引B树、B+树

程序员小灰 - 漫画：什么是B-树？ （注意查询、插入删除的图解）

程序员小灰 - 蛮会：什么是B+树？

MYSQL中的几种索引

MYSQL索引实现原理（重要）

B树与B+树

MYSQL索引原理详解

数据库索引为啥要用树结构做存储？

树的查询效率高，还可以做有序。

B+树的实现细节是什么？B-树和B+树有什么区别？联合索引在B+树中如何存储？

索引的数据结构

索引是一种数据结构。索引本身很大，不可能全部存储在内存中 ，因此索引 以索引表的形式存储在磁盘中 。

这样的话， 索引查找 过程中 就要产生磁盘I/O消耗 ，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

结点度（树的度）

结点拥有的子树数称为结点的度

1、B-树索引

B树（Balance Tree）是一种多路平衡查找树，他的 每一个节点最多包含M个孩子，M就是B树的阶。

M的大小取决于磁盘页的大小。

B-树就是B树，中间的横线不是减号，所以不要读成B减树。

m阶B树：

1、 树中 每个结点至多有m个子结点（即M阶）；

2、 若根结点不是叶子结点,则至少有2个子结点；

3、 除根结点和叶子结点外,其它每个结点至少有ceil(m/2)个子结点；

注：[ceil(m / 2)]个子结点（其中ceil(x)是一个取上限的函数）； 

即 中间节点最少有ceil(m/2)个子结点。

4、 所有叶子结点都出现在同一层 ，叶子结点不包含任何关键字信息；

5、有k个子结点的非终端结点恰好包含有k-1个关键字(单节点里元素).

每个节点中元素个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。( 即M阶树单节点最多有M-1个元素 )

每个结点中关键字从小到大排列， 并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划.

因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1.

B-树中的一个包含n个关键字,n+1个指针的结点的一般形式为：（n,P0,K1,P1,K2,P2,…,Kn,Pn） 其中：

a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。 

b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 

c)   关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

整理后：

m阶：

每个结点至多有m个子结点

根结点至少有2个子结点

中间节点至少有ceil(m/2)个子结点

所有叶子结点都出现在同一层

单节点最多有m-1个元素,一个节点的子节点数量会比元素个数多1

根二中C元减1

三阶B-树：

卫星数据：

指的是索引元素所指向的数据记录。比如数据库中的某一行。

B树中无论中间节点还是叶子节点都带有卫星数据。

B+树中，只有叶子节点带卫星数据，其他中间节点仅仅是索引 ，没有数据关联。

2、B+树索引

MYSQL使用B+树做索引。

三阶B+树：

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

1.有k个子树的 中间节点包含有k个元素（B树中是k-1个元素） ， 每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2. 所有的叶子结点中包含了全部元素的信息 ，及指向含这些元素记录的指针，且 叶子结点本身依关键字的大小自小而大顺序链接。

3. 每个父节点的元素都同时存在于子节点中，是子节点中的最大（或最小）元素。

根节点的最大元素是整个B+树的最大元素。

由于父节点的元素都包含在子节点，因此所有叶子节点包括了全部的元素信息。

每个叶子节点都带有指向下一个节点的指针，形成一个有序链表。

B+树的好处主要体现在查询性能上：

单行查询：

B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。

看起来跟B-树差不多，但其实有两点差别：

1、B+树中间节点没有卫星数据，所以同样大小的磁盘页上可以容纳更多节点元素。

这就意味着，数据量相同的情况下，B+树结构比B-树更加矮胖，因此 查询时IO会更少。

2、B+树的查询必须最终找到叶子节点，而B-树只需要找到匹配的元素即可 ，无论匹配元素是中间节点还是叶子节点。

因此B-树的查找性能不稳定（最好情况是只查根节点，最坏查到叶子节点），而B+树每次查找都是稳定点 。

范围查询：

B-树只能依靠 繁琐的 中序遍历 ，而 B+树只需要在链表上遍历 即可。

综合起来，B+树比B-树优势有三个：

1、IO次数更少

2、查询性能稳定

3、范围查询简便。

=====================================================================================