本文转载自微信公众号“Java代码”，作者Java代码。转载本文请联系码上Java公众号。前言在面试中，经常会问到索引相关的问题。其实索引的概念很好理解。我们上学的时候一定用过字典。索引就像字典的目录，我们可以通过目录快速检索到我们需要的词的解释。同理，在数据库中，索引也可以帮助我们快速的检索到我们需要的数据，查询效率非常高。一般来说，索引是一种数据结构。让我们探讨一下今天的索引是什么样的。为什么我们经常使用B+树作为索引最多的数据结构？为什么索引查询会变得更快？我们都知道数据库存储有两种存储介质，一种是内存，一种是硬盘。内存是一种临时存储介质，其容量是非常有限的。如果服务器断电，数据将丢失。硬盘是永久性的存储介质（如果没有损坏），所以我们需要将数据存储在硬盘中才能安全。但有一个问题？如果我们把数据放在硬盘里，当我们查询数据的时候，就会发生对硬盘的I/O操作。与内存访问相比，硬盘访问消耗的I/O时间要高得多。索引的作用是尽量减少对硬盘的I/O操作，从而减少所花费的时间。可以类比一下查字典的操作，目录（索引）可以帮你减少翻页的动作，是有原因的。先说二叉树。顾名思义，每个节点最多有两个“叉子”，即两个子节点，即左子节点和右子节点。但是二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。我们先来看下最基本的二叉搜索树（BinarySearchTree）。搜索节点与插入节点相同。我们假设要查找和插入的值是key：如果key大于根节点，则在右子树中查找；如果key小于根节点，则在左子树中查找；如果key等于根节点，即找到节点，则可以返回根节点。我们举个例子，创建一系列{30,25,36,32,40,20,28}，相同的数据，不同的插入顺序，树的结果是不同的，如下图：但是有是极端情况，当二叉树的深度很大时，可能会退化成链表。从上图可以看出，第一棵树的深度为3，也就是说最多只需要3次比较就可以找到结点，而第二棵树的深度为7，需要7次比较最多找到节点。图中右边也属于二叉搜索树，但是性能退化成了链表，找数据的时间复杂度变成了O(n)。如何解决这个问题呢？人们提出了平衡二叉搜索树（AVL树），给二叉搜索树加上约束，保证每个节点的左子树和右子树的高度差不能超过1，也就是说左子树和节点的右子树仍然是平衡二叉树。先说到这里吧。常见的平衡二叉树有很多种，包括平衡二叉查找树、红黑树、计数堆、伸展树等。平衡二叉搜索树是最早的自平衡二叉搜索树。当我们提到平衡二叉搜索树时，我们通常指的是平衡二叉搜索树。实际上，第一棵树是平衡二叉搜索树，搜索时间复杂度为O(log2n)。上面我们提到查询时间主要取决于硬盘的I/O操作。如果我们使用二叉树的形式，即使通过平衡二叉搜索树来改进，树的深度也是O(log2n)。当n比较大时，深度就比较高，比如下图中的情况：每访问一个节点，就需要进行一次磁盘I/O操作。对于上面的树，我们需要进行5次I/O操作。平衡二叉树虽然比较效率高，但是树的深度也高，这意味着磁盘I/O操作数高，会影响整体数据查询的效率。让我们看看什么是B树。上面我们知道，如果使用二叉树作为索引，树会变得很高，增加硬盘的I/O次数，影响数据查询的时间。B-tree的出现就是为了解决这个问题。B-tree的英文是BalanceTree，是一种平衡的多路搜索树。它的高度比平衡二叉树小得多。文件系统和数据库系统中的索引结构通常使用B树来实现。我们来看一下B-tree结构示意图，如下图所示：B-tree是一棵平衡的多路搜索树，它的每个节点最多可以包含M个子节点，M为称为B树的阶。如图所示，每个磁盘块都包含指向关键字和子节点的指针。如果一个磁盘块中包含x个关键字，那么指针的个数就是x+1。对于一个100阶的B-tree，如果有3层，最多可以存储100万条左右的索引数据。对于大量的索引数据，B树结构非常适合，因为树的高度比二叉树小很多。结合B-tree结构示意图，我们来看看B-tree是如何进行查找的。假设我们要找的关键字是9，步骤可以分为以下几步：我们和根节点的关键字(17,35)进行比较，如果9小于17，则得到指针P1；根据指针P1找到磁盘块2，关键是(8,12)，因为9在8和12之间，所以得到指针P2；根据指针P26找到磁盘块，关键字是(9,10)，然后我们找到了关键字9。可以看到在B树的查找过程中，我们并没有多次比较，而是如果将数据读出并在内存中进行比较，这个时间可以忽略不计。但是读取磁盘块本身就需要I/O操作，比在内存中进行比较所需要的时间消耗更多，这是影响数据查找时间的重要因素。与平衡二叉树相比，B树执行磁盘I/O操作。运算次数少，在数据查询上比平衡二叉树更高效。B-treePlus（B+树）B+树是在B-tree的基础上改进而来的。目前主流数据库都支持B+树作为索引方式。下面以MySQL为例，比较一下B+树和B-tree的区别：在B+树中，一个有k个子节点的节点有k个键。即子代数=关键字数，在B树中，子代数=关键字数+1。非叶节点的关键字同时存在于子节点中，并且是子节点中所有关键字中的最大值（或最小值）。在B+树中，非叶子节点仅用于索引，不保存数据记录，与记录相关的信息放在叶子节点中。在B树中，非叶节点既存储索引又存储数据记录。所有关键词都出现在叶子节点中，叶子节点组成一个有序链表，叶子节点本身按照关键词的大小从小到大依次链接起来。下图是一棵阶数为3的B+树，根节点中关键字1、18、35为子节点(1、8、14)、(18、24、31)、(35、41、53）分别。)中的最小值。每一层的父节点的关键字都会出现在下一层的子节点的关键字中，所以所有的关键字信息都包含在叶子节点中，并且每个叶子节点都有一个指向下一个节点的指针，所以A链接名单形成。比如我们要查找关键字16，B+树会从上到下逐层查找：与根节点的关键字(1,18,35)比较，16在1到18之间，得到指针P1(指向磁盘块2)找到磁盘块2，关键是(1,8,14)，因为16大于14，所以得到指针P3(指向磁盘块7)找到磁盘块7，key是(14,16,17)，然后我们找到了关键字16，所以我们可以找到关键字16对应的数据。整个过程一共进行了3次I/O操作。看起来B+树和B树的查询过程差不多，但是B+树和B树的根本区别在于B+树的中间节点不直接存储数据。这样做有什么好处？第一，B+树查询效率更稳定。因为B+树每次访问叶子节点只能找到对应的数据，而在B树中，非叶子节点也会存储数据，这会导致查询效率不稳定。有时可以访问非叶子节点查找关键字，有时则需要访问叶子节点查找关键字。其次，B+树的查询效率更高，因为B+树通常比B树更块（更大的阶数，更低的深度），并且查询需要更少的磁盘I/O。同样的磁盘页大小，B+树可以存储更多的节点键。不仅在单个关键字的查询上，在查询的范围上，B+树的效率也比B树高。这是因为所有的关键字都出现在B+树的叶子节点中，由一个有序链表链接起来。在B树中，需要中序遍历来完成查询范围的查找，效率要低很多。汇总磁盘I/O操作的数量对于索引的高效使用至关重要。传统的二叉树数据结构虽然查找数据效率高，但容易增加磁盘I/O操作次数，影响索引使用效率。因此，在构建索引时，我们更倾向于使用“chunky”数据结构。B-tree和B+树都可以作为索引的数据结构。在MySQL中，使用B+树。B+树在查询性能上更稳定。在磁盘页面大小相同的情况下，树的结构越短越胖。磁盘I/O次数较少，更适合关键字范围查询。
