MySQL*

索引*

B+ Tree*

1. 数据结构*

B 树指的是平衡树，平衡树是一颗查找树，并且所有叶子节点位于同一层。

B+ 树是基于 B 树和叶子节点顺序访问指针进行实现，具有 B 树的平衡性，并且通过顺序访问指针提高区间查询的性能。

在 B+ 树种，一个节点的 key 从左到右非递增排列，如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 都在范围内。

2. 操作*

进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

插入删除操作会破坏树的平衡性，因此在插入删除操作之后，需要对树进行一个分裂、合并、旋转等操作来维护平衡性。

3. 与红黑树比较*

红黑树等平衡树也可以实现索引，但文件系统和数据库系统普遍使用 B+ 树作为索引结构：

1. 更少的查找次数

平衡树查找操作的时间复杂度和树高 h 相关，$O(h) = O(\log_dN)$，d 为节点的出度。

红黑树出度为 2，而 B+ 树的出度一般非常大，所以红黑树的树高 h 比 B+ 树多，查找的次数多。

1. 利用磁盘预读特性

为了减少磁盘 I/O 操作，磁盘往往会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘预读时间，速度快。

内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得依次 I/O 就能完全载入一个节点。利用预读特性，相邻的节点也能够被预先载入。

MySQL 索引*

索引是在存储引擎层实现的。

1. B+ Tree 索引*

大多数 MySQL 存储引擎默认使用 B+ 树索引。

不需要全表扫描，只需要对树进行搜索即可，所以速度快很多。

B+ 树的有序性，还可用于排序和分组。

可以指定多个列作为索引列，多个索引列共同组成键。

适用于全键值、键值范围和键前缀查找，键前缀查找只适用于最左前缀查找。如果不是按照索引列的顺序进行查找，则无法使用索引。

InnoDB 的 B+ 树索引分为主索引和辅助索引，主索引的叶子节点 data 域记录着完整的数据记录，成为聚簇索引。辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找主键值，然后再到主索引中进行查找。

2. 哈希索引*

哈希表能以 $O(1)$ 时间查找，但失去了有序性，无法排序和分组，无法部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫 “自适应哈希索引”，当某个索引值被使用非常频繁时，会在 B+ 树索引之上再建立一个哈希索引。

3. 全文索引*

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。

查找条件使用 match against，而不是 where。

全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。

4. 空间数据索引*

MyISAM 存储引擎支持空间数据索引 (R-Tree)，可用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度进行组合查询。

索引优化*

1. 独立的列*