索引

1 索引类型

索引是在存储引擎中实现的，并不是所有的存储引擎都支持所有的索引类型。

大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构

1.1 存储引擎

• InnoDB
  • 聚簇索引
    • 聚簇(clustered)：数据行与叶子节点紧凑存储。
  • 辅助索引
    • 非聚簇索引（二级索引）都是辅助索引
    • 创建在聚簇索引之上，存储主键值，访问数据需要二次查找
• MyISAM
  • 非聚簇索引
    • 索引和数据是分开存储存储的，索引文件是缓存在 key_buffer 中，索引对应的是数据的磁盘位置，通过磁盘位置访问磁盘数据。
    • MyISAM 按照数据插入的顺序存储在磁盘上。实际上，MyISAM 中主键索引和其他索引在结构上没有什么不同。

1.2 聚簇索引

1）基本属性

• 术语“聚簇”表示数据行和相邻的键值聚簇的存储在一起。
• 一个表只能有一个聚簇索引。
• 索引选取顺序：
  • 有主键时，根据主键创建聚簇索引
  • 没有主键时，用一个唯一且不为空的索引列做为主键，成为此表的聚簇索引
  • 如果以上两个都不满足，则创建一个虚拟的聚集索引

2）提高数据访问性能

聚簇索引把索引和数据都保存到同一棵 B+ 树数据结构中，并且同时将索引列与相关数据行保存在一起。

聚簇意味着，当你访问同一数据页不同行记录时，已经把页加载到了 Buffer 中，再次访问的时候，会在内存中完成访问，不必访问磁盘。

3）使用顺序主键

使用 InnoDB 时应该尽可能地按照主键顺序插入数据，并且尽可能地使用单调增加的聚簇键的值来插入新行。

• 顺序主键（AUTO_INCREMENT）
  • 因为主键的值是顺序的，索引 InnoDB 把每一条记录都存储在上一条记录的后面。
  • 当达到页的最大填充因子时（InnoDB 默认的最大填充因子是页大小的 15/16，留出部分空间用于以后修改），下一条记录就会写入到新的页中。
  • 一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满（二级索引页可能不一样）。
• 稀疏主键（UUID）
  • 导致大量的磁盘 IO：写入的目标页可能已经数到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB 在插入之前不得不先找到并从磁盘读取目标页到内存中。
  • 影响多个页面：因为写入是乱序的，InnoDB 不得不频繁的做分页操作，以便为新的行分配空间。页分裂会导致移动大量数据，一次插入最少需要修改三个页面，而不是一个页。
  • 造成碎片：由于频繁的页分裂，页会变得稀疏，并且被不规则的填充，所以最终数据会有碎片。
  • 扫描变慢：聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。

4）使用小主键

如果主键比较大的话，那辅助索引将会变的更大，因为辅助索引的叶子存储的是主键值；过长的主键值，会导致非叶子节点占用占用更多的物理空间

1.3 辅助索引

• 非聚簇索引（二级索引）都是辅助索引。
• 辅助索引叶子节点存储的不再是行的物理位置，而是主键值。
• 通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据叶，再通过数据叶中的 Page Directory 找到数据行。
• 辅助索引访问数据总是需要二次查找。“自适应哈希索引”能够减少二次查找这样的重复工作。

1）复合索引

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

由多列创建的索引称为复合索引，在复合索引中的前导列必须出现在 where 条件中，索引才会被使用

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

2）前缀索引

• 当索引的字符串列很大时，创建的索引也就变得很大，为了减小索引体积，提高索引的扫描速度，就用索引的前部分字串索引，这样索引占用的空间就会大大减少，并且索引的选择性也不会降低很多。
• 对 BLOB 和 TEXT 列进行索引，或者非常长的 VARCHAR 列，就必须使用前缀索引，因为 MySQL不允许索引它们的全部长度。
• 列的前缀的长度选择很重要，又要节约索引空间，又要保证前缀索引的选择性要和索引全长度选择性接近。

3）唯一索引

唯一索引比较好理解，就是索引值必须唯一，这样的索引选择性是最好的

主键和唯一索引区别：

• 主键是主键约束 + 唯一索引
• 主键一定包含一个唯一索引，但唯一索引不是主键
• 唯一索引列允许空值，但主键列不允许空值
• 一个表只能有一个主键，但可以有多个唯一索引

2 B-tree、B+Tree

2.1 B-tree

• 平衡多路查找树：B指 Balance，和平衡二叉树稍有不同的是 B 树属于多叉树。
• 所有叶子节点均在同一层，叶子节点包含指向下一个叶子节点的指针，方便范围遍历。
• 数据记录为 [key, data]，key 为记录的键值；data 为数据记录除 key 外的数据。
• 顺序存储，叶子页到根的距离相同，适合查找范围数据。
• 查询必须从索引的最左边的列开始，不能跳过某一索引列。

2.2 B+Tree

• B+Tree 是在 B-Tree 基础上的一种优化，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。
  • 非叶子节点只存储键值信息。
  • 所有叶子节点之间都有一个链指针。
  • 数据记录都存放在叶子节点中。
• 通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。
• 因此可以对 B+Tree 进行两种查找运算：
  • 一种是对于主键的范围查找和分页查找
  • 另一种是从根节点开始，进行随机查找。
• 插入删除操作需要对树进行分裂、合并、旋转来维护平衡性。

2.3 与红黑树的比较

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因：

1）更少的查找次数

平衡树查找操作的时间复杂度等于树高 h，而树高大致为 O(h)=O(log_dN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。

2）利用磁盘预读特性

为了减少磁盘 I/O，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，速度会非常快。

操作系统一般将内存和磁盘分割成固态大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。

3 其它索引

3.1 哈希索引

哈希索引能以 O(1) 时间进行查找，但是失去了有序性：

• 无法用于排序与分组；
• 只支持精确查找，无法用于部分查找和范围查找。

自适应哈希索引

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

3.2 全文索引

• MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。
• 查找条件使用 MATCH AGAINST，而不是普通的 WHERE。
• 全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。
• InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。

3.3 空间数据索引

• MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。
• 必须使用 GIS 相关的函数来维护数据。

4 索引扫描方式

• 紧凑索引扫描
  • 在最初，为了定位数据需要做全表扫描
  • 为了提高扫描速度，把索引键值单独放在独立的数据的数据块里，并且每个键值都有个指向原数据块的指针
  • 因为索引比较小，扫描索引的速度就比扫描全表快，这种需要扫描所有键值的方式就称为紧凑索引扫描
• 松散索引扫描
  • 为了提高紧凑索引扫描效率，通过把索引排序和查找算法（B+trre），发现只需要和每个数据块的第一行键值匹配，就可以判断下一个数据块的位置或方向，因此有效数据就是每个数据块的第一行数据
  • 如果把每个数据块的第一行数据创建索引，这样在这个新创建的索引上折半查找，数据定位速度将更快。这种索引扫描方式就称为松散索引扫描。
• 覆盖索引扫描
  • 包含所有满足查询需要的数据的索引称为覆盖索引，即利用索引返回 select 列表中的字段，而不必根据索引再次读取数据文件

5 索引优化

5.1 独立的列

在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引。

5.2 前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符。

对于前缀长度的选取需要根据索引选择性来确定。

5.3 多列索引

在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。

最左匹配

5.4 索引列顺序

让选择性最高的索引列放在前面。

索引的选择性是指：不重复的索引值和记录总数的比值。最大值为 1，此时每个记录都有唯一的索引与其对应。选择性越高，每个记录的区分度越高，查询效率也越高。

5.5 覆盖索引

索引包含所有需要查询的字段的值。

具有以下优点：

• 索引通常远小于数据行的大小，只读取索引能大大减少数据访问量。
• 一些存储引擎（例如 MyISAM）在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用（通常比较费时）。
• 对于 InnoDB 引擎，若辅助索引能够覆盖查询，则无需访问主索引。

5.6 索引与加锁

InnoDB 仅对需要访问的元组加锁，而索引能够减少 InnoDB 访问的元组数。只有在存储引擎层过滤掉那些不需要的数据才能达到这种目的。

6 索引的优点

• 大大减少了服务器需要扫描的数据行数。
• 帮助服务器避免进行排序和分组，以及避免创建临时表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作。临时表主要是在排序和分组过程中创建，不需要排序和分组，也就不需要创建临时表）。
• 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）。

7 索引的使用条件

• 对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效；
• 对于中到大型的表，索引就非常有效；
• 但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。