1 构建索引需要考虑的因素

1.1 计算机存储结构

计算机存储结构如下图所示，从上到下依次为寄存器、高速缓存、主存储器、辅助存储器。其中主存储器，即我们常说的内存；辅助存储器也被称为外存，比较常见的就是磁盘、SSD等。在这个存储结构中，每一级存储的速度都比上一级慢很多，所以程序访问越上层存储中的数据，速度就会越快。

1.2 局部性原理与磁盘预读

• 起因：内存读写快，磁盘读写慢，而且慢很多；
• 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页（一般为4KB, MySQL为16KB）的数据，即每次加载更多的数据。如果未来要读取的数据就在这一页中，可以避免未来的磁盘I/O，提高效率；
• 局部性原理：软件设计要尽量遵循“程序运行期间所需要的数据比较集中”和“当一个数据被用到时，其附近的数据也通常会马上被使用”，这样磁盘预读能充分提高磁盘I/O。

1.3 索引设计考虑因素

数据库索引因数据量较大，一般都是存储于外存中，而程序是在内存中执行的，这样就需要进行频繁的I/O操作，那么，为了减少I/O次数，该怎么做呢？我们知道，磁盘预读是按页操作的，如果每一页包含的信息量足够大，是不是就可以达成目的了。

索引设计需要考虑的第一个核心因素：保证每页包含尽可能多的关键信息，来减少磁盘I/O

2 可提升查找性能的数据结构

添加索引的目的，主要是为了提升数据库的查找速度。一般来说，可提升查找速度的数据结构有以下两种：
（1）哈希。比如HashMap，其查询、插入、删除的平均时间复杂度均是O(1);
（2）树。比如二叉查找树，其查询、插入、删除的平均时间复杂度均是O(log(n))。

可以看到，论时间复杂度，不管是读请求，还是写请求，哈希的性能会更好，可为什么DB却选择使用B+树呢？接下来，我将按“哈希表 -> 平衡二叉树 -> B树 -> B+树”的思路逐个进行分析。

索引设计需要考虑的第二个核心因素：结合DB各种搜索场景，选取更合适的数据存储结构

3 哈希表

假设采用HashMap存储，如果查询sql都是单行查询，比如

select * from user where name='zhangsan';

那么，采用哈希确实很快，但是，如果过滤条件是范围（<、>）,排序（order by）等查询场景呢？其时间复杂度将退化为O(n)。假设我们采用的是“m叉查找树”，由于其本身是排好序的，其时间复杂度仍将是O(log(n))，即仍能保证其高效率。

所以，相比“m叉查找树”而言，后者更加合适。

哈希表：指定数据的定位较快，范围查询较慢

4 平衡二叉树（AVL树）

平衡二叉树的结构如下图所示，可以认为它是升级版的二叉树，它有两个特征：

• 数据是有序排列的
• 任何节点的儿子子树高度差的绝对值不会超过1

• 采用中序遍历可获得所有节点

  
  

从图中可以看出，每个节点有且仅能存储一个记录，如果数据量大的话，树的高度将会很高，故而，当查询数据时，会产生很多次磁盘I/O。

相比哈希表而言，平衡二叉树支持范围查询，解决了哈希表的痛点

5 B树（平衡多路查找树）

B树的结构如下图所示，它有以下特点：

• 叶子节点和非叶子节点都存储数据（此特点会导致非叶子节点不能存储大量的索引）

• 采用中序遍历亦可获得所有节点

  
  

从图中可以看出，每一个节点可以有多个子节点，且每一个节点（包括非叶子节点）均存储数据，采用中序遍历便可查找到所有数据。但是，数据库磁盘交互是按页为单位（MySQL默认为16K）的，如果数据量过多时，每个节点存储的键值会较少，进而树的高度比较高，导致磁盘I/O比较多。同时，在实际项目中，范围查询的SQL比较频繁，倘若采用B树作为索引结构，需要中序遍历很多节点，来收集符合筛选条件的数据集。因此，此结构某种程度来看，不是太合适。

6 B+树

B+树的结构如下图所示，它有以下特点：

• B树的升级版
• 非叶子节点仅保存索引和指针（不再存储数据），仅叶子节点存储数据信息（保证节点可以存储更多索引，进而减少树的高度）

• 叶子节点间采用了链表，这样，范围查询时，只要确定范围的左右边界坐标，遍历叶子节点链表，便可获取所有符合条件节点集合

  
  

从其特点可得知，它兼具了“降低树高度，减少磁盘I/O”、“提升范围查询性能”两个因素。

接下来，举一个例子来说明B+树怎么控制树的高度的。
我们假设一页大小是16KB，每个索引（主键）是bigint类型，即8B，指针为6B。那么每页能存储大约1000个索引（16KB/(8B+6B) 1000）。
那么，一颗3层的B+树能够存储多少索引呢？如下图：

大约能够存储10亿个索引。通常 B+ 树的高度在2-4层，由于 MySql 在运行时，根节点是常驻内存的，因此每次查找只需要大约2-3次IO。

7 番外篇 —— 索引构建注意事项

结合索引的底层原理，我们在实际项目中构建索引时，需要注意以下几点：

• 主键不能太大，否则，每个节点可容纳的节点会较少
• 主键最好是自增的，否则，每次插入都会调整B+树，从而导致页分裂，影响性能

参考资料：
[1] BTree和B+Tree详解 https://www.cnblogs.com/vianzhang/p/7922426.html
[2] Mysql的常见面试题 + 索引原理分析 https://www.cnblogs.com/hulianwangjiagoushi/p/10537909.html
[3] 数据库索引融会贯通 https://juejin.im/post/5c67becf6fb9a049a42f9420
[4] 数据库索引为什么用B+树实现 https://juejin.im/post/5c67bf756fb9a049e4133cd9
[5] 20分钟数据库索引设计实战 https://juejin.im/post/5c67bf296fb9a049a81fdbde
[6] 数据库索引，到底是什么做的 https://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651961486&idx=1&sn=b319a87f87797d5d662ab4715666657f&chksm=bd2d0d528a5a84446fb88da7590e6d4e5ad06cfebb5cb57a83cf75056007ba29515c85b9a24c&mpshare=1&scene=1&srcid=0228KnNLEEqCDuKngwvMur4c&key=d1883245a7b0616ccde09505e7184e8a33fad3848d4f804f91885bdad93a1b2aea22333148db09073f09f8c977e09f871a3cdc9c546be12bbe6b44a1d66fc209efeb4cb3a1f5eff2dd240556723964b3&ascene=0&uin=MjMwMzU4MDU2MQ%3D%3D&devicetype=iMac+MacBookPro12%2C1+OSX+OSX+10.14+build(18A391)&version=12020810&nettype=WIFI&lang=zh_CN&fontScale=100&pass_ticket=WOB52g58BXxtmtWDGbQLQhPhwwKkAErjlrx2uOM5oMnULMc9fOC9ptI%2BaWQpLWVs
[7] MySql 三大知识点——索引、锁、事务 https://maimai.cn/article/detail?fid=1188457423&efid=b6VprMXHZGlLNLckx8yfAQ