再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她
|
副标题[/!--empirenews.page--]
索引这个词，相信大多数人已经相当熟悉了，很多人都知道MySQL的索引主要以B+树为主，但是要问到为什么用B+树，恐怕很少有人能把前因后果讲述的很完整。本文就来从头到尾介绍下数据库的索引。 索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。 索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义，如果我想要在[1,2,3,4]中找到4这个数据，直接对全数据检索也很快，没有必要费力气建索引再去查找。索引在mysql数据库中分三类： B+树索引、Hash索引、全文索引 我们今天要介绍的是工作开发中最常接触到innodb存储引擎中的的B+树索引。 要介绍B+树索引，就不得不提二叉查找树，平衡二叉树和B树这三种数据结构。B+树就是从他们仨演化来的。 二叉查找树 首先，让我们先看一张图
从图中可以看到，我们为user表(用户信息表)建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。 键对应user表中的id，数据对应user表中的行数据。二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。 如果我们需要查找id=12的用户信息，利用我们创建的二叉查找树索引，查找流程如下：
利用二叉查找树我们只需要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树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。 （编辑：核心网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
