终于有篇看的懂的B树文章了！

索引，信托大大都人已经相等认识了，许多人都知道 MySQL 的索引首要以 B+ 树为主，可是要问到为什么用 B+ 树，生怕很少有人能把前因效果报告完备。本文就来从新到尾先容下数据库的索引。

图片来自 Pexels

索引是一种数据布局，用于辅佐我们在大量数据中快速定位到我们想要查找的数据。

索引最形象的比喻就是图书的目次了。留意这里的大量，数据量大了索引才显得故意义，假如我想要在 [1,2,3,4] 中找到 4 这个数据，直接对全数据检索也很快，没有须要艰辛气建索引再去查找。

索引在 MySQL 数据库平分三类：

B+ 树索引

Hash 索引

全文索引

我们本日要先容的是事变开拓中最常打仗到的 InnoDB 存储引擎中的 B+ 树索引。

要先容 B+ 树索引，就不得不提二叉查找树，均衡二叉树和 B 树这三种数据布局。B+ 树就是从他们仨演化来的。

二叉查找树

起首，让我们先看一张图：

从图中可以看到，我们为 user 表(用户信息表)成立了一个二叉查找树的索引。

图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。键对应 user 表中的 id，数据对应 user 表中的行数据。

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

假如我们必要查找 id=12 的用户信息，操作我们建设的二叉查找树索引，查找流程如下：

将根节点作为当前节点，把 12 与当前节点的键值 10 较量，12 大于 10，接下来我们把当前节点>的右子节点作为当前节点。

继承把 12 和当前节点的键值 13 较量，发明 12 小于 13，把当前节点的左子节点作为当前节点。

把 12 和当前节点的键值 12 比拟，12 便是 12，满意前提，我们从当前节点中取出 data，即 id=12，name=xm。

操作二叉查找树我们只必要 3 次即可找到匹配的数据。假如在表中一条条的查找的话，我们必要 6 次才气找到。

均衡二叉树

上面我们讲授了操作二叉查找树可以快速的找到数据。可是，假如上面的二叉查找树是这样的结构：

这个时辰可以看到我们的二叉查找树酿成了一个链表。假如我们必要查找 id=17 的用户信息，我们必要查找 7 次，也就相等于全表扫描了。

导致这个征象的缘故起因着实是二叉查找树变得不服衡了，也就是高度太高了，从而导致查找服从的不不变。

为了办理这个题目，我们必要担保二叉查找树一向保持均衡，就必要用到均衡二叉树了。

均衡二叉树又称 AVL 树，在满意二叉查找树特征的基本上，要求每个节点的阁下子树的高度差不能高出 1。

下面是均衡二叉树和非均衡二叉树的比拟：

由均衡二叉树的结构我们可以发明第一张图中的二叉树着实就是一棵均衡二叉树。

均衡二叉树担保了树的结构是均衡的，当我们插入或删除数据导致不满意均衡二叉树不服衡时，均衡二叉树会举办调解树上的节点来保持均衡。详细的调解方法这里就不先容了。

均衡二叉树对比于二叉查找树来说，查找服从更不变，总体的查找速率也更快。

B 树

由于内存的易失性。一样平常环境下，我们城市选择将 user 表中的数据和索引存储在磁盘这种外围装备中。

可是和内存对比，从磁盘中读取数据的速率会慢上百倍千倍乃至万倍，以是，我们该当只管镌汰从磁盘中读取数据的次数。

其它，从磁盘中读取数据时，都是凭证磁盘块来读取的，并不是一条一条的读。

假如我们能把只管多的数据放进磁盘块中，那一次磁盘读取操纵就会读取更大都据，那我们查找数据的时刻也会大幅度低落。

假如我们用树这种数据布局作为索引的数据布局，那我们每查找一次数据就必要从磁盘中读取一个节点，也就是我们说的一个磁盘块。

我们都知道均衡二叉树然则每个节点只存储一个键值和数据的。那声名什么?声名每个磁盘块仅仅存储一个键值和数据!那假如我们要存储海量的数据呢?

可以想象到二叉树的节点将会很是多，高度也会极其高，我们查找数据时也会举办许多次磁盘 IO，我们查找数据的服从将会极低!

为了办理均衡二叉树的这个破绽，我们应该探求一种单个节点可以存储多个键值和数据的均衡树。也就是我们接下来要说的 B 树。

B 树(Balance Tree)即为均衡树的意思，下图等于一棵 B 树：

图中的 p 节点为指向子节点的指针，二叉查找树僻静衡二叉树着实也有，由于图的雅观性，被省略了。

图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的根基单元都是页，以是我们这里叫做页更切合 MySQL 中索引的底层数据布局。

从上图可以看出，B 树相对付均衡二叉树，每个节点存储了更多的键值(key)和数据(data)，而且每个节点拥有更多的子节点，子节点的个数一样平常称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。

基于这个特征，B 树查找数据读取磁盘的次数将会很少，数据的查找服从也会比均衡二叉树高许多。

若是我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：

先找到根节点也就是页 1，判定 28 在键值 17 和 35 之间，那么我们按照页 1 中的指针 p2 找到页 3。

将 28 和页 3 中的键值对较量，28 在 26 和 30 之间，我们按照页 3 中的指针 p2 找到页 8。

将 28 和页 8 中的键值对较量，发明有匹配的键值 28，键值 28 对应的用户信息为(28，bv)。

B+ 树

B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的布局图：

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!