面试官：索引是什么？一般又是如何实现的呢？

索引是为了提高数据查询的效率，就像书的目录一样。一本500页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，很难快速找到相关内容。同样，对于数据库的表而言，索引其实就是它的“目录”。

数据库索引是数据库系统中提高数据检索效率的关键机制，通过特定的数据结构来组织数据，使得查询操作能更快定位到要查找的记录。

索引的实现依赖于高效的数据结构，常见的有以下几种：

1、Hash

利用哈希函数将键转换为固定长度的哈希码，然后通过哈希码直接定位记录，适用于等值查询，查询速度快，但不支持范围查询。

哈希索引适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

2、有序数组

有序数组则在等值查询和范围查询方面表现优异，等值查询使用二分法就可以快速得到，这个时间复杂度是O(log(N))；因为是有序数组范围查询的效率自不必说。

但是，在更新数据的时候就很麻烦，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。所以，有序数组索引只适用于静态存储引擎，存储不会修改的数据。

3、二叉搜索树

二叉搜索树的特点是：父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值，查询的时间复杂度是O(log(N))。为了维持O(log(N))的查询复杂度，需要保持这棵树是平衡二叉树，这样，更新的时间复杂度也是O(log(N))。

但是，索引不止存在内存中，还要写到磁盘上。如果树高30，一次查询可能需要访问30个数据块，磁盘I/O会大大拖慢查询性能。

4、BTree（平衡多路搜索树）

有二叉就有多叉，B树这是一种自平衡的树数据结构，B树由于存在多叉，可以大大降低树的高度，减少一次请求中访问磁盘的次数。B树的每个节点包含键值、数据及其指向子节点的指针。如下图所示：

5、B+Tree

B+Tree是B Tree的一种变体，B+Tree 只在叶子节点存储数据，而 B 树的非叶子节点也要存储数据。它的所有叶子节点包含了全部数据记录的指针（或直接存储数据），并且叶子节点间通过双向指针相连，形成了一个双向链表，特别适合范围查询和全表扫描。如下图所示：

面试官：MySQL InnoDB引擎的索引采用的是哪种数据结构？原因是什么？

MySQL的InnoDB存储引擎是其默认的事务型存储引擎，广泛应用于需要高并发和数据一致性的场景。InnoDB对于索引的实现，主要采用了B+Tree数据结构，原因如下：

1、适应磁盘I/O特性

B+Tree结构能够很好地适配磁盘读取的块操作特性。由于磁盘I/O通常是按块进行的，B+Tree的每个节点可以存放多个键值对，这样每次磁盘I/O都可以读取更多的数据，减少磁盘访问次数，提高效率。

2、支持范围查询和排序

B+Tree的所有叶子节点通过指针相连，形成一个有序链表，这使得范围查询和数据排序变得非常高效，无需额外的排序操作。

3、聚簇索引

InnoDB表是基于聚簇索引（Clustered Index）构建的，即数据行与主键索引存放在一起，如果主键被定义为索引，则B+Tree的叶子节点直接包含表数据，进一步提高了数据访问速度。

4、二级索引支持

除了聚集索引，InnoDB还支持二级索引（Secondary Index），二级索引的叶子节点包含指向主键的指针，即使在非主键索引上也能高效地找到对应的数据行。

综上所述，MySQL InnoDB引擎采用B+Tree作为索引的数据结构，主要是因为它在磁盘I/O效率、范围查询支持、以及数据存储布局上的优势，这些特性共同保证了InnoDB引擎在处理大量并发事务和复杂查询时的高性能。

面试官：一棵B+树到底可以存放多少条数据呢？

一个3层的B+树就可以存放超过 2 千万条数据了。查找数据的时候，一次页的查找代表一次 I/O，当我们通过主键索引查询的时候，一般只需要3 次 I/O 就可以了。

怎么计算的呢？

假如我们的主键 ID 是 bigint 类型，长度为 8 个字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。所以非叶子节点（一页16K）可以存储 16384/14=1170个这样的单元（键值+指针）。

如果一条数据大小是1K，那么叶子节点可以放 16 条数据。

树深度为3的时候，可以存储的数据为1170*1170*16=21902400条记录。

结语

索引的基本原理是大多数面试官都会考察的知识点，大家一定要牢记。熟悉了基本原理，很多问题也都能迎刃而解了，比如模糊搜索、对列进行运算等场景，索引为什么会失效？

因为这些场景下，MySQL此时无法利用B+树判断去哪个子树找数据了，B+树的特性无法被利用了，因此MySQL只能去遍历所有数据了。这样考虑后，问题是不是就简单很多啦。

索引相关的知识点很多，下一篇我们主要介绍下索引的几种分类，什么是聚簇索引、二级索引，覆盖索引又是怎么一回事儿呢，敬请期待！

参考：

[1]https://juejin.cn/post/6904293886626103309