那些年与面试官交手过的数据库索引

我坐在面试官的对面，声情并茂的做着自我介绍，面试官小哥哥面无表情的翻看着我的简历。不知道是小哥哥过于高冷仍是被我的简历招引，2分钟了，小哥哥仍是没有和我讲一句话。嘤嘤嘤~看起来似乎有两下子。不过无所谓，这些都不重3 , _ [要。

什么是索引？

面试官：我看你项目中有做过 SQL 优化，那咱们今日就来聊聊索引吧。

（索引能问些啥，无非是索引的概念、索引的运用规则、索引的分类、索引的原理。嘻嘻~我早有预备）
我：v T 2 数据库中的索引，简略来说呐，就好比一本书的目录，它A | $能够帮咱们快速进行特定值的定位与查找，从而加快数据查询的功率。

假如咱们不运用索引，就必须从第 1 条记载开端依次往后查J % W g @ 6找，直到把一切的数据表都查找完，才干找到想要的数据。

面试官：那照c m J你这么说，索引是不是越多越好？

索引是不是越多越好？

我：当然 9 7 d X索引也不是越多越好，索引也不是全能的，在有些状况下运用索引反而会让功率变低。

索引7 ! y , ` ~ { A的价值是帮咱们从海量数据中找到想要的数据，假如数据量少，那么是否运用索引对结果的影响并不大, ? v J 4 U 0。

在数据表中的数据行数比较少的状况下，比方不到 1000 行，是不需求创立索引的。另外，当数据重复度大，比方高于 10% 的时分，也不需求对这个字段运用索引。

比方，假如是性别这个字段，就不需求对它创| ` + h u 5 m立索引。这是为什么呢？假如你想要在 100 万行数据中查找其间的 50 万行（比方性别为男的数据），一旦创立了索* U [ A引，你需求先拜访 50 万次索引，然后再拜访 50 万次数据表，这m V m M {样加起来的开支比不运用索引可能还要大。

索引的品种

面试官点点头，看Z X v起来对我以上的答复还算满足。接着又问：

面试官：那你说说索引有哪些品种？

（嘻嘻，关于索引的品种我太熟了。但A w W s F & 1我仍是稍稍顿了顿开端了我的答复。）

依照功能逻辑分类

我：从功能逻辑上说，索引首要有 4 种，分d N ? n别是一般索引、仅有索引、t 4 z ! Q k H O主键索引和全文索引。

一般索引是根底的索引，没有任何束缚，首要用于进步查询功率。

仅有索引便是在一H S P ` a 2 z !般索引的根底上增加了7 h ] v 5 a ;数据仅有性的束缚，在一张数据表里能够有多个仅有e F w 2 X %索引。

主键索引在仅有索引的根底上增加了不为空的n % Z束缚，也便是 NOT NULL+UNIQUE，一张表里最多只要一个主键索引。

全文索引用的不多，MySQL 自带的全文索引只支撑英文。咱们一般能够选用专门的全9 r 4 # e . K $ Z文查– f u *找引擎，比方 ES(ElasticSearch) 和 Solr。

其实前三种索3 b @ P y引（一般索引、仅有索引和主键索引）都是一类索引，只不过对数据的束% J O f n m 4缚性逐渐提高。

在一张数据表中只能有一个主键索引，这是由主键索引的物理完结方法决议的，由于数据存储在文件中只能依照一种次序进行[ F G Y S Y P T存储。但能够有多个$ 2 v 0 ] i一般索引或许多个仅有索引。

依照物理完s J 1 – A t 7结方法分X $ | c类

我：依照物理完结方法，t D 6 ,索引能够分为~ H _ U 2 种：集合索引和非集合N [ v d w - ,索引。咱/ ~ } N们也把非集合索引称为# F ` r 1 p i二级索引或许辅助索引。

集合索引Y # 8 E 3 i能够依照主键来排序存储数据，这样在查找行的时分十分有效。

举个比方，假如是一本汉语字典，咱们想要查找“数”这个字，直| C W D U j m m接在书中找汉语拼音的方位即可，也便是拼音“shu”。这样找到了索引的方位，在它后边便是咱们想要找的数据行。

非集合索引不会把索引指向的内容像集合索引相同直接放到索引的后边，S } h [ 8而是维护独自的索引表（只维护索引，不维护索引指向的数据7 v 7 q），为数据检索提供方便。

咱T f 9 w – 0 8 W们还以汉语字典为例，假如想要查找“数”字，那么依照部首查找的方法，先找到“数”字的偏旁部首，然后这个目录会告诉咱们“数”字寄存到第多d s V N H ) n Q少页，咱们再去指定的页码找这个字。

也便是说体系会进行两次查找，第一次先找到索引，第二次找到索引对应的方位取出数据行。

集合索引和非集合索引二者的差异

其实答复到上面已经能够了，可是为了展现自己理解的透彻，我还做了以下阐述：

我：集合索引与非集合索引的原理不同，在运用上也有一些差异：

1. 集合索3 K s : p S引的叶子节点存储的便是咱们的数据记载，非集合索引的叶子节K Q $ A 1 ` a ^ D点存储的是数据方位。非集合索引不会影响数据表的物理存储次序。

2. 一个表只能有一个集合索引，由于只能有一种排序存储的方法，但能够有多个非集合索引，也便是* = Z多个索引目录提供数据检索。

3. 运用集合索引的时分，数据的查询功率高，但假如对数据进行$ H D ^ 0 [ L刺进，删除，更新等操作，功率会比非集合索引低。

索引的数据结构

面试官：你方才从功能逻辑和物理完结的方法阐述了索引的分类，看来对F D ` I Q索引的数据结构是有了解的，说G d K 5 + % g一说你知道的索引数据结构就有哪些。

（这个简略啊，D h U E我信口开河）

我：Hash、B 树和 B+ 树都能够作为索引的数据结构，可是在 MySQL 中选用的是4 1 g } ; k : B+ 树，B+ 树也是咱们常用的索引数据结构。

为什么咱& D g L ] h _ f n们常用 B+ 树作为索引的数据结构？

面试官：为什么咱们常用 B+ 树作为索引的数据结构R N : 3 ？其它树形结构不香吗？

（我就知道没那么简略。唉，我方才为什么要提“常用”俩字呢？我心里哭笑不得，但仍是强作镇定。）
我：在答X e # 1 & 8 $复这个问题之前我先说一下索引的寄存方d & M位，以j I D及索引的数据结构设计好坏的评t a H K : T D判规范。

索引的寄存方位y d y =

我：咱6 + W们知道，数据库服务器有两种存储介质，分别为硬S N H {盘和内存。内存归于暂时存储，当发生意外时，比方说断电或许发生故障重启，会造成数据丢失；硬盘相当于永e H 0 L N 3久存储介质，数据可耐久化，这也是为什么咱们需求把数据保存到硬z V 6盘上。

怎么评价索引的数据结构设计好坏？

我：虽然内存的读取速度很快，但咱们仍是需求将索引寄存到硬盘上。因而( H L I，当咱们在硬盘上进行查询时，也就产生了硬盘的 I/O 操作。

咱们都知道，硬盘的 I/O 存取耗费的时刻比较于内存的存取来说，要高许多。咱们经过索引来查找某行数据的时分，需求核算产生的磁盘 I/O 次数L 6 * } C S J k，当磁盘 I/O 次数越多，所耗费的时刻也就越大。

假如咱们能让索引的数据结构尽量削减硬盘的 I/O 操作，所耗费的时刻也就越小，那么这个索引a i h z 5 5的数据结构设计的也就越优。

二J 5 叉树

面试官点点头暗示我继续说下去，为了对“为什么咱们常用 B+ 树作为索引的数据结构”这个问题进行一个小白都能看懂的满足答复，我拿起了笔，图文并茂的从二叉树开端和面试官扯了起来。
我：接下来说说二叉树，咱们知道二分查找法是一种高效的数据检索方法，时刻复杂度为 O(log2n)，能够说检索速度是很快了。

以最根底的二叉查找树（Bin9 v o ! mary Search Trt p E o z Yee）为例，查找某个节点和刺进节点的规则相同，咱们假定查找刺进的数值为 key：

1. 假如 key 大于根节点，则在右子树中进行查找；
2. 假如 key 小于根节点，则在左子树中进行查找；
3. 假如 key 等于根节点，也便是找到了这个节点，回来根节点即可。

举个比方，咱4 ! _ j W O们对数列（25，18，36，9，20，32，41）发明出来的二分0 [ ] ] p O F C q查找树如下图所示~ A f：

可是存 * / L r在特别的状况，二叉树的深度会十分大。比方咱们给出的数据次序是 (9, 18, 20, 25, 32, 36, 41)，发明出来的二分查找树如下图所示：

现在这棵树也归于二分查找树，可是性能上已经退化成了一条链表，查找数据的时刻复杂度变成了 O(n)。

咱们能够看出来第一个树的深度是 3，也便是说最多只需 3 次比较，就能够找到节点，而第二个树的深度是 7，最多需求 7 次比较才干找到节点。

平衡二叉查找树

面试官：已然一般的二叉树不行，那平衡二叉查找树怎么样？由于咱们知道它能够经过旋转的方法防止数据结构在特别状况下退化成链表。T e v %

我：我方才提到过，数据查询的时刻首要依赖于磁盘 I/O 的次数，即使是用了改善后的平衡二叉查找树，树的深度也是 O(log2n)8 0 ?，当 n 比较大6 & q J时，深度也是比较高的，比方下图的状况：

每拜访一次节点就需求进行一次磁盘 I/O 操作: 9 – E 9，关于上面的树来说，咱们需求进行 5 次 I/O 操作。虽然平衡二叉树比O ; ( E J Y较的功率高，可是树的深度也相同高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的功率。

什么是 B 树？

我：针对上面相同的数据，假如咱们把二叉树改成M Q v D 1 – M 叉树（M>2）的话，当 M=3 时，相同的 31 个节点能够由下面的三叉树来进行存储：

你能6 v +看到此时树的高度降低了，当数据量 N 大的时分，以及树的分叉数 M 大的时分q W r / z 8 S U，M 叉g L l Y树的高度会远小于二叉树的高度。

假如V 7 M ) i # Q 9 q用二] ~ ? W # / l W @叉树作为索引的完结结构，会让树变得很高，增加硬盘的 I/O 次数，影响数据查询的时刻。因而一个节点就不能只要 2 个子节点，而应该答应有 M 个子节点 (M>2)。

而B 树的呈现便是为了解决这个问题，B 树的英文是 Balance Tree，也便是平衡的多路查找树，它的高度远小于平衡二叉树的高度。在文件体系和数据库体系中的索引结构经常选用 B 树来完结。

B 树的结构如下图所示：

B 树作R f I c 7 : g *为平衡的多路查找树，它的每一个节点最q l I多能够包含 M 个子节% 8 0 q点，M 称为 B 树的阶。8 K ? ?一同你能看到，每个磁盘块中包含了要害字和子节点的指针。假如一个磁盘块中包含了 x] c G 5 B 个要害字，那么指针数便是 x+1。关于O V { n /一个 100 阶的 B 树来说，假如有 3 层的话最多能够存储约 100 万的索引数据。关于大量的索引数据来说，选用 B 树的结构是十分合适的，由于树的高度, W U C . D要远小于二叉树的高度。

一个 M 阶的 B 树（M>2）有以下的特性：

1. 根节点的儿子数的范围是 [2,M]。
2. 每个中心节点包含 k-1 个要害字和 k 个孩子，孩子的数量 = 要害字的数量 +1，k 的取值范围为 [ceil(M/2), M]。
3. 叶子节点包含 k-1 个要害字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
4. 假定中心h } ? U节点节点的要害字为：Key[1], Key[2], …, Key[k-1]} G 6，且要害字依照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个要害字相当于划分了 k 个范围，也便是对应着 k 个指针，即为：P[1], P[2], …, P[k]，其间 P[1] 指向要害C f B %字小于 Key[1] 的子树，P[i] 指向要害字归C r A g $ _ ~ / G于 (Key[i-1], Key[i]) 的子树，P[k] 指向要害字大于 Key[k-1] 的子树。
5. 一切叶子节B u I n j ~ U B 点位于V o Q k 4同一层。

上面那张图所表明的 B 树便是一棵 3 阶的 B 树。咱们能够看下磁盘块 2，里边的要害字为（8，12），它有 3 个孩子 (3，5)，{ # , k(9，10) 和 (13，15)，你能看到 (3，5) 小于 8，(9，10) 在 8 和 12 之间，而 (13，15) 大于 12，刚好符合方才咱们给出的特征。

然后咱们来看下怎么用 B 树进行查找。假定咱们想要查找的要害字是 9，那么进程能够分为以下几步：

1. 咱们与根节点的要害字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
2. 依照指针 P1 找到磁盘块 2，要害字为（8，12），由于 9 在 8 和 12 之间，所以咱们得到指针 P2；
3. 依照指针 P2 找到磁盘块 6，要害字为（9，10），然后咱们找到了要害字 9。

咱们能够看出来在 B 树的查找进程中，咱们比较的次数并不少，但假如把数据读取出来然后在内存中进行比较，这个时刻便是能够忽略不计的。

而读取磁盘块自身需求进行 I/O 操U ^ 4作，耗费的时刻比在内存中进行比较所需求的时刻要多，是数据查找用时的重要因素，B 树比较于平E l . B a R v衡二叉树来说磁盘 I/O 操作要少，u K s { _ 1在数据查询中比平衡二叉树功率要高。

什么是 B+ 树？

我：在最终说说 B+ 树，B+ 树是根据 R Y @ B 树做出了改善，干流的 DBMS 都支撑 B+ 树的索引方法，比方 MySQL。B+ 树和 B 树的差异在于以下几点：

1. 有 k 个孩子的节点就有 k 个要害字。也便是孩子数量 = 要害字数，而 B 树中，孩子数量 = 要害字数 +1。
2. 非叶子节点的要害字也会一同存在在子节点中，而且是在子节点中一切要害h ~ : T U U ] R字的最大（或最小）。
3. 非叶子节点仅用于索引，不保存数据记载，跟记0 ~ )载有关的信息都放在叶子节点中。而 B 树中，非叶子节点既L 4 v K g ] B保存索引j h S，也保存数据记载。
4. 一切要害字都在叶7 q z 7 s }子节点呈现，叶子节点构成一个有序链表，而且叶子节点自身依照要害字的巨细从小到大次序链c 2 w 0 P q接d R 2 ? / z。

下I 8 4 8 v ^ c 5 #图便是一棵 B+ 树，阶数为 3，根节点中的要害字 1、18、35 分别是子节点（1，8，14），（18，24，31）和（3Y | 1 F !5，41，53）中的最小值。每一层父节点的要害字都会呈现在下一层的子节点的要害字中，因而在叶子节点中包含了一切的要害字信j H t w 2 .息，而且每一个叶C ` h T子节点都有一个指向下一个节点的指针，这样就形成了一个链表。

比方，咱们想要查找要害字 16，Bi 8 ; k u+ 树会自顶向下^ ~ %逐层进行查找：

1. 与= @ L j V z $根节点的要害字 (1，8 z 8 ) o E18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）
2. 找到磁盘块 2，要害字为（1D – ] X { , 5 E，8，14），由于 16 大于 14，所以得到指针 P3（指向磁盘块 7）
3. 找到磁盘块 7，要害字为（14，16，17），然后咱们找到了要害字 16，所以能够找到要害字 16 所对应的数据。

面试官：B+ 树整个进程总共进行了 3 次 I/O 操作，看起来 B+ 树和 B 树的查询进程差不多，那为什么咱们运用 B+ 树更多呢？

我：B+ 树和 B 树有个根本的差异在于，B+ 树的中心节点并不直接存储数据。这样的好处是：

• 首要，B+ 树查询功率更稳定。由于 B+ 树每次只要拜访到叶子节点才干找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这0 9 a i D j &样就会造成查询功率不稳定的状况，有时分拜访到了非叶子节点就能够找到要害字，而有时需求拜访到叶子节点才干找到要害字。

• 其次，B+ 树的查询功率更高，这D 8 1 @ j是由于一般 Bl ` O 8 a K D j {+ 树比 B 树更矮胖（M ! p阶数更大，深度更低L R 1 y i 4 ]），查询所需求的磁盘 I/O 也会更少。相l ; 9 D k同的磁盘页巨细，B+ 树能够存储更多的节点要害字。

不仅是对单个要害字的查询上，在查询范围上，B+ 树的功率也比 B 树高。这是E % s / :由于一切要害字都呈现在 B+ 树的叶子节点中，并经过有序x j + G { b链表进行了链接。而在 B 树中则需求经过中序遍历才干完结查询范围的查找，功率要低许多。

（说到这里我自己都满足的想哭，完了我还不忘了总结）

总的来说，磁盘的 I/O 操作次数对索引的运用功率至关重要。虽然传统的二叉树数据结构查找数据的功率高，但很容易增加磁盘 I/O 操作的次数，影响索引运用的功率。因而在构n ( f n G } O u 3造索引的时分，咱们更倾向于选用“矮胖A G r”的数据结构。

B 树和 B+ 树都能够% l T作为索引的数据结构，在 MySQL 中选用的{ F o o k e z –是 B+ 树，B+ 树在查询性能上更稳定，在磁盘页巨细相同的状况下，树s W : G ^ M的构造愈加矮胖，所需求进行的磁盘 I/O 次数更少% o y，更合适进行要害字的范围查询。

面试官拿起周围已经凉透的咖啡，喝了一口。

（这小姑娘有点东西呀）

「继续更新……」

爱心三连

最终，感谢各位的阅读。文章的意图d d y W q V是记载和分享，若文中呈现明显疏忽也欢迎指出，咱们一同在探讨中学习。不胜感激 ！

假如你觉得本文对你有用，那就给个「赞」吧，你的鼓励和支撑是我行进路上的动力~

欢迎重视我的微信大众号【后端程序媛】，咱们一同探讨代码与人生。

另外，我建了一个技术沟通群，欢迎我们进群学习沟通。

文章参考

1. 《数据结构与算法》；
2. 极客时刻：SQL必知必会。