mysql 节点查根_（三）B数、B+树及在数据库索引中应用

在算法逻辑上，二叉树的查找效率和比较次数都是最小的，但是在实际问题中，还要考虑磁盘IO.

数据库索引是存储在磁盘上的，当数据量比较大时，索引可能几个G。

当我们利用索引查询的时候，不能将整个索引全部加载到内存中，能做的只能是逐一加载每一个磁盘页，这里的磁盘页对应索引树的节点。

二叉查找数、平衡二叉树、红黑树是典型的二叉查找数结构，其查找的时间复杂度为O(log2N)与树的深度有关，所以降低树的深度自然能提高查找效率。

在实际场景中：大规模数据存储中，实现索引查询这样一个实际场景下，树节点存储的元素数量是有限的(如果元素数量非常多的话，查找退化成节点内部的线性查找了)，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而降低查询效率低下，所以就思考如何降低树的深度(当然不能减少查询的数据量)，一个基本的想法是：采用多叉树结构

B树和B+树是平衡的多路查找树

一、B树

简单来说：B树是一种多路平衡查找树，它的每一个节点最多包含k个孩子，k也称为阶树。

k的大小取决于磁盘页的大小

概念：B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)，数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点;

规则：

(1)排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；

(2)子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外(注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉)；

(3)关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);

(4)所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

用途：

文件系统和部分数据库索引，比如著名的非关系型数据库MongoDB

最后我们用一个图和一个实际的例子来理解B树(这里为了理解方便我就直接用实际字母的大小来排列C>B>A)

高度每下降一级，即读取一次磁盘(一次I/O)；当一个磁盘页数据读取到内存，对一个节点内数据查找，速度很快，几乎可以忽略。所以树的高度足够低，I/O次数足够少，就能提升性能。

B树的查询流程：

如上图我要从上图中找到E字母，查找流程如下

(1)获取根节点的关键字进行比较，当前根节点关键字为M，E

(2)拿到关键字D和G，D

(3)拿到E和F，因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null)；

考题：M阶B-树中含有N个关键字，最大深度为：

至于为什么不能叶节点不能存储关键字，查看如下原因：

叶子结点是不存在的，指向这些结点的指针为空，引入叶子结点的目的是为了方便分析B-树的查找性能

一棵3阶B-树中含有2047个关键字,包含叶结点层,该树的最大深度为(12)

二、B+树

B+树的性能比B树更高

1.与B树区别：

①有n棵子树的节点含有n个关键码

②所有的叶节点中包含了全部关键码的信息，以及指向含有这些关键码记录的指针，且叶子节点本身依关键字大小自小而大顺序连接

③所有的非终端节点可以看成是索引部分，节点中仅含有其子树根节点中最大(小)的关键字

对③理解

卫星数据：索引元素所指向的数据记录，比如数据库中的某一行。在B树中，无论是中间节点还是叶子节点都有卫星数据。

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

在B+树中，通常有两个头指针，一个指向根节点，另一个指向关键字最小的叶节点。因此，可以对B+数进行两种查找运算：一种是从最小关键字开始顺序查找，另一种是从根节点进行随机查找。

查找过程与B树类似，但是有两点不同(也是查找效率更优的原因)

①B+树的中间节点，没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素【 “更矮胖”，查询时IO次数更少】

②B+树必须查找到叶子节点，而B树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点

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

2.B+树的优势

单一节点存储更多元素，io更少

所有查询都要查找到叶子节点，查找性能稳定

所有叶子节点形成有序链表，便于范围查询

3.B+树应用场合

大部分的关系数据库，如Mysql

三、为什么B+树比B树更适合实际应用中操作系统的文件索引和数据库索引

因为数据表的索引比较大，不能常驻内存，所以以文件形式存储在磁盘中。当查询数据的时候就需要I/O操作。高效率查询的目标是较少的I/O次数。一次I/O一般是读取一页大小的数据。当申请一个节点时，就以页的大小来申请。也就是说一次I/O可以读取一个节点的数据。这样，B树也可以作为索引数据结构，但是最终还是选择了B+树。

①B+树的内部节点并没有指向关键字具体信息。因此可以存储更多的数据。索引树更加矮胖，I/O次数更少

②B+树的查询效率更加稳定

由于非终节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以任何关键字的查找必须从根节点到叶子节点。所有关键字查询路径长度相同，导致每一个数据的查询效率相当。

③范围查找简单：B+树不需要中序遍历，遍历链表即可。

四、hash比B+树更快，为啥mysql还用B+树来存索引

和具体的业务场景有关，如果只选一个数据，那确实hash更快。但是数据库中经常会选择多条，这时B+树索引就更快了。

而且数据库中索引一般放在磁盘中，数据量大的情况，无法一次装入内存，B+数的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。