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
网友评论