数据库索引笔记

一句话简单来说，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本500页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，那我估计你可得找一会儿。同样，对于数据库的表而言，索引其实就是它的“目录”。

几种索引的常见模型

实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多，以下是三种常见、也比较简单的数据结构：

• 哈希表
• 有序数组
• 搜索树

哈希表

哈希表是一种以 键-值（key-value）存储数据的结构，我们只要输入待查找的值（key），就可以找到其对应的值（Value）。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

而不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。当要找某个 Value 的时候先算出哈希再顺序遍历找到需要的值。

需要注意的是，不管是哈希还是后面的链表，存放值的时候都不是有序的，虽然这样增加数据的时候速度很快，但是如果要做区间查询速度会很慢，需要全部扫描一遍。因此，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

顾名思义，是一种按顺序存放数据的数组结构。有序数组在等值查询和范围查询场景中的性能就都非常优秀。

正因为是顺序的，等值查找的时候用二分法很快就能得到，这个时间复杂度是 O(log(N))。区间范围搜索则用二分法定位第一个值，然后向右遍历，直到超出范围则退出循环。如果仅仅看查询效率，有序数组就是最好的数据结构了。

但是，在需要更新数据的时候就麻烦了，为了保持有序，无序插入记录时就要挪动后面所有的记录，成本太高。所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

二叉搜索树、N叉树

二叉搜索树是很经典的数据结构，它的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。如果要查询某个值，通过对比大小可以避免遍历所有的值。这个时间复杂度是 O(log(N)) 。

但是有一个经典的问题，当数据是按特定顺序插入的时候，数据都会往其中一边一直插入（左小右大原则），几乎变成了链表，这时它的搜索性能已经是线性的了。

于是乎为了维持 O(log(N)) 的查询复杂度，二叉搜索树就需要保持自己是平衡二叉树。不过其更新的时间复杂度也是 O(log(N)) 。

至此，二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上，树的不同结点很可能不在磁盘的同一页中，所以还要考虑到磁盘的寻址加载次数。

既然树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。同一层的节点多了，树的深度就不用那多大了，从而减少了磁盘寻址加载的次数。

假设一棵100万节点的平衡二叉树，树高20。一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说，对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20个10ms的时间，这个查询效率明显被拖慢了。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用 “N叉”树 。这里的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。再有，其实树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

B树

B树（B-Tree）是一种平衡多叉搜索树，B就是Balanced（平衡的）的意思。

和多叉树一样，B树的所有节点都可以存放数据，不过在多叉树的基础上通过重新组织节点，降低树的高度，从而减少IO读写次数来提升效率。

B树的特点：

• B树的叶子结点和非叶子节点都会存放数据或主键等，也叫做关键字，用于搜索对比。
• 搜素性能等价于在全集内做一次二分查找。
• 所有的叶子节点都在同一层。
• 每个根节点至少2个子女。
• 每个非根节点所包含关键字个数 j 满足：⌈m/2]-1 ≤ j ≤ m−1（m为树的阶）
• 非根节点的所有节点（不包括叶子节点）的度数正好是关键字总数加1，子树个数 k ：⌈m/2⌉ ≤ k ≤ m（m为树的阶）

B+树

B+树是B树基础上的一种变体，也是一种多路搜索树，主要区别特征有以下：

• 数据都存在叶子结点上面，父节点上的是关键字索引，是子节点上最大或者最小的元素。
• 每个叶子节点都有一个指针，指向下一个数据，形成一个有序链表。
• 非叶子结点仅具有索引作用，当搜索时，B+树只可能在叶子节点命中被查询的数据，不能在非叶子节点命中。

B+树中间节点没有Data数据，所以同样大小的磁盘页可以容纳更多的节点元素。所以数据量相同的情况下，B+树比B树更加“矮胖”，因此使用的IO查询次数更少，更适合文件系统。

B树和B+树的插入、删除过程

关于B树和B+树数据的插入、删除、页分裂、页合并等等知识点参考这位大佬的博文 ->
B树和B+树的插入、删除图文详解

再发展还有B*树，是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

不管是哈希、有序数组，再到N叉树、B树、B+树等，它们都是不断迭代、不断优化的产物或者解决方案。数据库技术发展到今天，跳表、LSM树等数据结构也被用于引擎设计中，这里就不再一一展开了。

在MySQL中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。以下用常用的InnoDB存储引擎为例，分析其索引模型，以后遇到问题时再举一反三，根据不同索引的模型分析问题、解决问题。

InnoDB 的索引模型

在InnoDB存储引擎中，每张表都有个主键。

1. 如果我们定义了主键(PRIMARY KEY)，那么InnoDB会选择主键作为聚集索引。
2. 如果没有则判断表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主键。如果多个，取第一个。
3. 如果不符合上述条件，InnoDB存储引擎自动创建一个6字节大小的ROWID作为隐含的聚集索引（ROWID随着行记录的写入而主键递增，这个ROWID不像ORACLE的ROWID那样可引用，是隐含的）。

表都是根据这个主键顺序组织存放的，这种存储方式的表称为索引组织表(index organized table IOT)。

InnoDB默认索引结构使用 B+ 树作为索引模型（空间索引采用R树，此处不引申），数据记录本身被存于主索引（B+Tree）的叶子节点上。

参考博文

• 林晓斌 – MySQL实战45讲
• Mysql索引整理总结