前言每当我们执行某条SQL，发现它很慢的时候，都会下意识地反映是否加了索引，那么你有没有想过为什么要加一个索引会使数据的查找速度变快，那么索引的底层一般用什么结构来存储呢？相信你看了标题已经有了答案，是的！B+树！那么它和普通的链表、哈希等有什么区别，为什么大多数存储引擎选择使用它。今天给大家揭秘B+树。相信看完这篇文章，B+树不再神秘了。下面的高频面试题，对你理解会有很大的帮助！为什么索引经常使用B+？树作为底层数据结构除了B+树索引，你还知道什么索引吗？为什么推荐自增id作为主键呢？主键不是自建的吗？什么是pagesplittingandpagemerging如何根据索引查找行记录下面我们用几种常见的数据结构对比来解释一下B+树定义问题分页合并定义问题要知道索引底层为什么要用一个B+树，这取决于它解决了什么问题。我们可以考虑一下。我们每天用的比较多的SQL有哪些？假设我们有如下用户表：CREATETABLE`user`(`id`int(11)unsignedNOTNULLAUTO_INCREMENT,`name`varchar(20)DEFAULTNULLCOMMENT'name',`idcard`varchar(20)DEFAULTNULLCOMMENT'IDnumber',`age`tinyint(10)DEFAULTNULLCOMMENT'age',PRIMARYKEY(`id`))ENGINE=InnoDBDEFAULTCHARSET=utf8COMMENT='用户信息';一般我们有以下需求：1.根据用户id查询用户信息select*fromuserwhereid=123;2.根据区间值查找用户信息select*fromuserwhereid>123andid<234;3、按id倒序排列，分页提取用户信息select*fromuserwhereid<1234orderbyiddesclimit10;从上面的普通SQL我们可以看出索引使用的数据结构必须满足以下三个条件。根据一定的值进行准确快速的查找。根据区间值上下限快速查找该区间的数据指标值。索引值需要排序，支持快序查找和倒序查找。接下来，我们以主键索引（idindex）为例，看看如何用对应的数据结构构造键值（Keyvalue），并直接访问该数据结构，这样可以让键值映射到对应的通过哈希函数转换得到哈希表的位置，查找效率很高。哈希索引是基于哈希表实现的。假设我们已经为姓名建立了哈希索引，查找过程如下图所示：对于每一行数据，存储引擎会计算所有索引列（上图中的姓名列）的哈希码（上图中哈希表的位置），哈希表中的每个元素都指向数据行的指针，由于索引本身只存储对应的哈希值，索引的结构非常紧凑，使得哈希索引搜索速度非常快！但是哈希索引也有它的缺点，如下：对于哈希索引，只有与索引的所有列完全匹配的查询才是有效的。比如我在(A,B)列上建立了一个哈希索引，如果只查询数据A列，这个索引是不能用的。hash索引不是按照索引值的顺序存储的，所以不能用于排序，也就是说不能按照区间快速查找。哈希索引只包含哈希值和行指针，不存储字段值，因此不能使用索引，但是由于哈希索引大多是在内存中完成的，所以在大多数情况下这不是问题。哈希索引只支持相等比较查询，包括=、IN()，不支持任意范围内的查找，比如age>17综上所述，哈希索引只适用于特定的场合。如果使用得当，确实可以带来很大的性能提升。例如，在InnoDB引擎中，有一个特殊的功能叫做“自适应哈希索引”。如果InnoDB注意到某些索引列值被频繁使用，它会在基于内存的B+树索引之上创建哈希索引，这样B+树也可以拥有哈希索引的优势，比如快速哈希查找。2、链表双向链表支持顺序查找和反向查找，如下图所示，但是显然不支持我们说的按某个值或区间快速查找。另外，我们知道表中的数据会不断增加，索引也必须及时插入更新，链表显然不支持快速插入数据，那么能不能在链表的基础上修改一下列表使其支持快速搜索、更新和删除。有一种结构刚好可以满足我们的需求，这里就引入跳表的概念。什么是跳表？简单的说，跳表就是在链表之上加上多层索引构成的。如下图所示，假设我们现在要查找7-13区间的记录，不再需要从头开始查找。我们只需要在上图中的二级索引中开始查找，遍历三次就可以找到链表的区间位置。时间复杂度为O(logn)，速度很快。从这点来看，跳表就可以满足我们的需求了。其实它的结构和B+树很接近，只不过B+树是从平衡二叉搜索树演化而来的。就这样，我们一步步看看如何将平衡二叉搜索树转化为B+树。我们先来看看什么是平衡二叉搜索树。一棵平衡二叉搜索树具有以下性质：如果左子树不为空，则左子树上所有节点的值都小于其根节点的值；如果右子树不为空，则右子树上所有节点的值都大于等于其根节点的值；每个非叶子节点的左右子树高度差的绝对值（平衡因子）至多为1。下图是一棵平衡二叉搜索树。从其特点可以看出，在平衡二叉搜索树中寻找一个节点的时间复杂度为O(log2n)。现在我们将其转化为B+树。您可以看到主要区别在于所有节点。这些值都在最后一个叶子节点上用双向链表连接在一起。仔细对比跳表，是不是很像？现在如果我们要查找15~27范围内的数，只需要先找到节点15（时间复杂度logn=3次）然后从前向后遍历，直到节点27，就可以找到节点中的这个区间，从而完美支持我们的三个需求：快速搜索值、区间、顺序和反向搜索。假设有1亿个节点，每个节点需要查询多少次，显然最多log210亿=27次，如果这1亿个节点都在内存中，那么27次显然不是问题，可以说速度很快，但是新的问题出现了。这1亿个节点的内存大小是多少？让我们做一个简单的计算。假设每个节点为16字节，1亿个节点会占用1.5G左右的内存！对于内存这样宝贵的资源来说，是一种可怕的空间消耗。这只是一个索引。一般我们会在表中定义多个索引，或者在库中定义多个表。这样内存很快就满了！所以fullyload一个B+树索引明显是有问题的，怎么解决。我们不能把它存在内存中，所以我们可以把它放在磁盘上。磁盘空间比内存大很多，但是新的问题又出现了。我们知道内存和磁盘的读取速度相差太大。通常，内存在纳秒级别。磁盘是毫秒级别的，在读取同样大小的数据时两者可能相差数万倍，所以我们上一步计算的27个query如果放在磁盘上是非常致命的（找到一个节点可以认为是一次）磁盘IO，也就是说有27个磁盘IO！），27个查询可以优化吗？可以很明显的观察到query的个数和树高有关，树高和什么有关，而且很明显和每个节点的子节点个数有关，也就是N个中的N个-叉树。假设现在有16个数，我们分别用二叉树和五叉树来构建。可以看到，如果使用二叉树，需要遍历5个节点。如果使用五叉树，只需要遍历3次，就可以节省两次磁盘IO。回顾上面的1亿个节点，如果我们用100叉树来搭建，需要多少IO？可以看到最多遍历五次（其实根节点一般都保存在内存中，所以可以认为是4次）！磁盘IO从27减少到5！性能可以说是有了很大的提升。有人说5倍还是太多了，有可能吗？将100-forktree改成1000或10000-forktree，这样可以进一步减少IO的数量。这里我们需要了解页面（page）的概念。在计算机中，无论??是内存还是磁盘，操作系统都是根据页面的大小来读取的（页面大小通常为4kb）。Read会将连续的数据提前读入内存，从而避免多次IO。这就是计算机中著名的局部性原理，即如果我使用一条数据，很可能这条数据附近的数据也会被读取。使用它，简单地一起加载，以免因为多个IO而拖慢速度。这个连续数据有多大？它必须是操作系统页面大小的整数倍。这个连续的数据就是一个MySQL页面。默认值是16KB，也就是说，对于B+树的节点，最好设置页大小（16KB），这样B+树上的一个节点只会有一次IO读取。那么有人会问了，页面大小是不是越大越好？设置越大，节点能容纳的数据越多，树高越小，IO越小。这里需要注意的是，页面大小并不是越大越好，InnoDB通过内存中的缓冲池（poolbuffer）来管理从磁盘读取的页面数据。如果pagesize过大，cachepool很快就会满，可能会导致内存和磁盘之间页面频繁的换入换出，影响性能。通过上面的分析，相信我们不难猜到N叉树中N是怎么设置的，只要尽量保证每个节点的大小等于一个页面的大小（16kb）即可选择时。Pagesplittingandpagemerging现在我们来看一开始的问题。为什么推荐自增id作为主键？自建主键不好吗？有人可能会说，用户的身份证是唯一的，可以作为主键。假设身份证为主键，有什么问题？B+树为了保持索引的顺序，每次插入或更新记录时都会更新索引。假设原来基于身份证索引的B+树如下（假设是二叉树，图中只列出了身份证的前四位）。现在在db中插入了一条以3604开头的身份证对应的记录。更新索引，按照顺序更新，显然3604的ID号应该插在左边节点3504的后面（如下图，假设是二叉树）如果3604的ID号是插入到3504后面，这个节点的元素个数为3，显然不满足二叉树的条件，此时会进行分页，所以需要调整这个节点，使其满足条件二叉树，如图：经过调整，满足二叉树的条件。这种由分页引起的调整必然会导致性能下降，尤其是使用身份证作为主键时。如果使用自增id作为主键，由于新插入的表中生成的id大于索引中所有的值，要么合并到已有节点中（元素个数不full)，或者放到一个新创建的节点中（如下图），所以如果使用自增id作为主键，就不会有分页的问题。值得推荐！如果有页面拆分，则必须有页面合并。页面合并什么时候发生？，当表记录被删除时，索引也被删除，此时可能会发生页合并。如图，当我们删除id为7和9对应的行时，上图中的索引会更新，7、9被删除。这时候8和10应该合为一个节点。否则8和10分散在两个节点上，可能会造成两次IO读取，势必影响查找效率！页面合并什么时候发生？可以设置一个阈值。例如，对于一棵N叉树，当节点数小于N/2时，应该与附近的节点合并。但是需要注意的是，合并后节点中的元素大小可能会超过N，导致分页，需要调整父节点等，使其满足N叉树的条件。如何根据索引查找行记录？相信看完上面B+树索引的介绍，大家应该还是有疑惑的。如何根据对应的索引值查找行记录。其实就是把对应的行记录放在最后一个叶子节点，found索引值，也就是找到了行记录。从图中可以看出，非叶子节点只存储索引值，最后一行只存储行记录，大大减小了索引的大小，而且只要找到索引值，找到行记录，也提高了效率，这种把整行记录存储在一个叶子节点中的索引称为聚簇索引，其他的称为非聚簇索引。关于B+树的总结综上所述，B+树有以下特点：每个节点中子节点的个数不能超过N，也不能小于N/2（否则会造成分页或者分页合并）子节点的子节点根节点的个数不能超过m/2，属于例外情况。m-ary树只存储索引，并不实际存储数据。只有最后一行的叶子节点存储行数据。叶子节点通过链表连接在一起，方便按区间查找。小结本文从日常生活中常用的SQL由浅入深总结了B+树的特点。相信大家对B+树索引应该有比较清晰的认识，所以我说为什么要掌握底层呢？学完B+树，再看前几题。事实上，仅此而已。深入挖掘底层有时会让你保持原样。
