牛油们 ，数据库索引与二叉树来啦，转载自马尾，努力看完呐！

什么是索引？

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

（索引能问些啥，无非是索引的概念、索引的使用规则、索引的分类、索引的原理。嘻嘻~我早有准备）  我：数据库中的索引，简单来说呐，就好比一本书的目录，它可以帮我们快速进行特定值的定位与查找，从而加快数据查询的效率。

如果我们不使用索引，就必须从第 1 条记录开始依次往后查找，直到把所有的数据表都查找完，才能找到想要的数据。

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

索引是不是越多越好？

我：当然索引也不是越多越好，索引也不是万能的，在有些情况下使用索引反而会让效率变低。

索引的价值是帮我们从海量数据中找到想要的数据，如果数据量少，那么是否使用索引对结果的影响并不大。

在数据表中的数据行数比较少的情况下，比如不到 1000 行，是不需要创建索引的。另外，当数据重复度大，比如高于 10% 的时候，也不需要对这个字段使用索引。

比如，如果是性别这个字段，就不需要对它创建索引。这是为什么呢？如果你想要在 100 万行数据中查找其中的 50 万行（比如性别为男的数据），一旦创建了索引，你需要先访问 50 万次索引，然后再访问 50 万次数据表，这样加起来的开销比不使用索引可能还要大。

索引的种类

面试官点点头，看起来对我以上的回答还算满意。接着又问：

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

（嘻嘻，对于索引的种类我太熟了。但我还是稍稍顿了顿开始了我的回答。） 

按照功能逻辑分类

我：从功能逻辑上说，索引主要有 4 种，分别是普通索引、唯一索引、主键索引和全文索引。

普通索引是基础的索引，没有任何约束，主要用于提高查询效率。

唯一索引就是在普通索引的基础上增加了数据唯一性的约束，在一张数据表里可以有多个唯一索引。

主键索引在唯一索引的基础上增加了不为空的约束，也就是 NOT NULL+UNIQUE，一张表里最多只有一个主键索引。

全文索引用的不多，MySQL 自带的全文索引只支持英文。我们通常可以采用专门的全文搜索引擎，比如 ES(ElasticSearch) 和 Solr。

其实前三种索引（普通索引、唯一索引和主键索引）都是一类索引，只不过对数据的约束性逐渐提升。

在一张数据表中只能有一个主键索引，这是由主键索引的物理实现方式决定的，因为数据存储在文件中只能按照一种顺序进行存储。但可以有多个普通索引或者多个唯一索引。

按照物理实现方式分类

我：按照物理实现方式，索引可以分为 2 种：聚集索引和非聚集索引。我们也把非聚集索引称为 二级索引或者辅助索引。

聚集索引可以按照主键来排序存储数据，这样在查找行的时候非常有效。

举个例子，如果是一本汉语字典，我们想要查找"数"这个字，直接在书中找汉语拼音的位置即可，也就是拼音"shu"。这样找到了索引的位置，在它后面就是我们想要找的数据行。

非聚集索引不会把索引指向的内容像聚集索引一样直接放到索引的后面，而是维护单独的索引表（只维护索引，不维护索引指向的数据），为数据检索提供方便。

我们还以汉语字典为例，如果想要查找"数"字，那么按照部首查找的方式，先找到"数"字的偏旁部首，然后这个目录会告诉我们"数"字存放到第多少页，我们再去指定的页码找这个字。

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

聚集索引和非聚集索引二者的区别

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

我：聚集索引与非聚集索引的原理不同，在使用上也有一些区别：

1. 聚集索引的叶子节点存储的就是我们的数据记录，非聚集索引的叶子节点存储的是数据位置。非聚集索引不会影响数据表的物理存储顺序。

2. 一个表只能有一个聚集索引，因为只能有一种排序存储的方式，但可以有多个非聚集索引，也就是多个索引目录提供数据检索。

3. 使用聚集索引的时候，数据的查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚集索引低。

索引的数据结构

面试官：你刚才从功能逻辑和物理实现的方式阐述了索引的分类，看来对索引的数据结构是有了解的，说一说你知道的索引数据结构就有哪些。

（这个简单啊，我脱口而出）

我：Hash、B 树和 B+ 树都可以作为索引的数据结构，但是在 MySQL 中采用的是 B+ 树，B+ 树也是我们常用的索引数据结构。

为什么我们常用 B+ 树作为索引的数据结构？

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

（我就知道没那么简单。唉，我刚才为什么要提"常用"俩字呢？我内心哭笑不得，但还是强作镇定。）  我：在回答这个问题之前我先说一下索引的存放位置，以及索引的数据结构设计好坏的评判标准。

索引的存放位置

我：我们知道，数据库服务器有两种存储介质，分别为硬盘和内存。内存属于临时存储，当发生意外时，比如说断电或者发生故障重启，会造成数据丢失；硬盘相当于永久存储介质，数据可持久化，这也是为什么我们需要把数据保存到硬盘上。

如何评价索引的数据结构设计好坏？

我：虽然内存的读取速度很快，但我们还是需要将索引存放到硬盘上。因此，当我们在硬盘上进行查询时，也就产生了硬盘的 I/O 操作。

我们都知道，硬盘的 I/O 存取消耗的时间相比于内存的存取来说，要高很多。我们通过索引来查找某行数据的时候，需要计算产生的磁盘 I/O 次数，当磁盘 I/O 次数越多，所消耗的时间也就越大。

如果我们能让索引的数据结构尽量减少硬盘的 I/O 操作，所消耗的时间也就越小，那么这个索引的数据结构设计的也就越优。

二叉树

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

以最基础的二叉搜索树（Binary Search Tree）为例，搜索某个节点和插入节点的规则一样，我们假设搜索插入的数值为 key：

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

举个例子，我们对数列（25，18，36，9，20，32，41）创造出来的二分查找树如下图所示：

但是存在特殊的情况，二叉树的深度会非常大。比如我们给出的数据顺序是 (9, 18, 20, 25, 32, 36, 41)，创造出来的二分搜索树如下图所示：

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

我们可以看出来第一个树的深度是 3，也就是说最多只需 3 次比较，就可以找到节点，而第二个树的深度是 7，最多需要 7 次比较才能找到节点。

平衡二叉搜索树

面试官：既然普通的二叉树不行，那平衡二叉搜索树怎么样？因为我们知道它可以通过旋转的方式避免数据结构在特殊情况下退化成链表。

我：我刚才提到过，数据查询的时间主要依赖于磁盘 I/O 的次数，即使是用了改进后的平衡二叉搜索树，树的深度也是 O(log2n)，当 n 比较大时，深度也是比较高的，比如下图的情况：

每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5 次 I/O 操作。虽然平衡二叉树比较的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。