索引简介

要做 sql 性能优化或想深入了解存储引擎，就需要了解索引。

MySQL 官方对索引的定义为：索引（Index）是帮助 MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构。可以简单理解为“排好序的快速查找数据结构”。

下图就是一种可能的索引方式示例：

左边的表格是数据表，一共有两列七条记录，表格最左边的是数据记录的物理地址

为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在一定的复杂度内获取到相应数据，从而快速的检索出符合条件的记录。

除了数据本身之外，数据库还维护着一个满足特定查找算法的数据结构，这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法，这种数据结构就是索引。

一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件形式存储磁盘上

索引的优缺点

优点:

  • 类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的 IO 成本

  • 通过索引列对数据进行排序，降低数据排序的成本，降低了 CPU 的消耗

缺点:

  • 实际上索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也是要占用空间的

  • 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行 INSERT、UPDATE 和 DELETE。 因为更新表时，MySQL 不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段， 都会调整因为更新所带来的键值变化后的索引信息

索引结构

1、Hash

加速查找速度的数据结构，常见的有两类：

  • 哈希，例如 HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1)；
  • 树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N)；

可以看到，不管是读请求，还是写请求，哈希类型的索引，都要比树型的索引更快一些，

那为什么，索引结构要设计成树型呢？

想想范围/排序等其它 SQL 条件：

哈希型的索引，时间复杂度会退化为 O(n)，而树型的“有序”特性，依然能够保持 O(log2N) 的高效率。

注意：InnoDB 并不支持哈希索引。

2、时间复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

3、普通二叉树

二叉树的特点：

  • 一个节点只能有两个子节点，也就是一个节点度不能超过 2

  • 左子节点 小于 本节点；右子节点大于等于本节点

对该二叉树的节点进行查找

  • 深度为 1 的节点的查找次数为 1，

  • 深度为 2 的节点的查找次数为 2，

  • 深度为 N 的节点的查找次数为 N，

结论：因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3 次

4、平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为 AVL 树（有别于 AVL 算法），且具有以下性质：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在 O(logN)。但是频繁旋转会使插入和删除牺牲掉 O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。

5、BTree

B-Tree 树即B 树，B 即 Balanced，平衡的意思。

B 树的阶：节点的最多子节点个数。

子节点：

B 树的搜索，从根结点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点；重复这一过程，直到所对应的子指针为空，或已经是叶子节点。

关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据，搜索有可能在非叶子节点结束，其搜索性能等价于在关键字全集内做一次二分查找

那么，我们思考一个问题，索引树会一次性加载吗？

  • 数据库索引是存储在磁盘上的，如果数据很大，必然导致索引的大小也会很大，超过几个 G（好比新华字典字数多必然导致目录厚）
  • 当我们利用索引查询时候，是不可能将全部几个 G 的索引都加载进内存的，我们能做的只能是：
  • 逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点。

页

Page是Innodb存储的最基本结构，也是Innodb磁盘管理的最小单位，与数据库相关的所有内容都存储在 Page 结构里。

Page 分为几种类型：数据页（B-Tree Node），Undo 页（Undo Log Page），系统页（System Page），事务数据页（Transaction System Page）等；

每个数据页的大小为 16kb，每个 Page 使用一个 32 位（一位表示的就是 0 或 1）的 int 值来表示，正好对应 Innodb 最大 64TB 的存储容量(16kb * 2^32=64tib)

块

系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

InnoDB 存储引擎中有页（Page）的概念，系统一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘 I/O 次数，提高查询效率。

Btree 的查询流程

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。

模拟查找关键字 29 的过程：

  • 根据根节点找到磁盘块 1，读入内存。【磁盘 I/O 操作第 1 次】
  • 比较关键字 29 在区间（17,35），找到磁盘块 1 的指针 P2。
  • 根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I/O 操作第 2 次】
  • 比较关键字 29 在区间（26,30），找到磁盘块 3 的指针 P2。
  • 根据 P2 指针找到磁盘块 8，读入内存。【磁盘 I/O 操作第 3 次】
  • 在磁盘块 8 中的关键字列表中找到关键字 29。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而 3 次磁盘 I/O 操作是影响整个 BTree 查找效率的决定因素。

BTree 相对于 AVLTree 每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。

6、B+Tree

B+树是 B 树的变体，也是一种多路搜索树。B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子节点才命中（B 树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找

所有关键字都出现在叶子节点的链表中（即数据只能在叶子节点），且链表中的关键字(数据)恰好是有序的。因此不可能在非叶子节点命中, 非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储（关键字）数据的数据层

通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。 因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

InnoDB 存储引擎中页的默认大小为 16KB，（innodb 的全部数据文件（后缀为 ibd 的文件），他的大小始终都是 16384（16k）的整数倍。）

计算

一般一棵 B+树最多能够存放多少行数据？

假设 B+树高为 2，即存在一个根节点和若干个叶子节点，假设一行记录的数据大小为 1k

那么这棵 B+树的存放总记录数为：**根节点指针数 * 单个叶子节点记录行数**

其中，单个叶子节点（页）中的记录数=16K/1K=16

接着计算出非叶子节点能存放多少指针，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节）。假设主键 ID 为 BIGINT 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节（14B），一个页中能存放多少这样的单元，其实就表明有多少指针，即 16384/14=1170。那么能够算出一棵高度为 2 的 B+树，能存放 1170*16=18720 条这样的数据记录。

根据一样的原理能够算出一个高度为 3 的 B+树能够存放：

因此在 InnoDB 中 B+树高度通常为 1-3 层，它就能知足千万级的数据存储。在查找数据时一次页的查找表明一次 IO，因此经过主键索引查询一般只须要 1-3 次 IO 操做便可查找到数据。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。

MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 I/O 操作。

BTree 和 B+Tree 比较

  • B树结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B 树的深度较大，增大查询时的磁盘 I/O 次数进而影响查询效率。
  • B+树中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+树的高度。

7、聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。

聚簇索引就是按照每张表的主键构造一颗 B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。

Innodb 通过主键聚集数据，如果没有定义主键，innodb 会选择非空的唯一索引代替。如果没有这样的索引，innodb 会隐式的定义一个主键来作为聚簇索引。

优点：

  • 如果查询的数据刚好命中，因为聚簇索引将索引和数据保存在同一个 B+树中，此时聚簇索引获取数据比非聚簇索引更快
  • 聚簇索引对于主键的排序查找和范围查找速度非常快

缺点：

  • 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义一个自增的 ID 列为主键
  • 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于 InnoDB 表，我们一般定义主键为不可更新
  • 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

8、非聚簇索引

在聚簇索引之上创建的索引称之为非聚簇索引，非聚簇索引访问数据总是需要二次查找。非聚簇索引叶子节点存储的不再是行的物理位置，而是主键值。通过非聚簇索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的 Page Directory 找到数据行。

Innodb 非聚簇索引的叶子节点并不包含行记录的全部数据，叶子节点除了包含键值外，还包含了相应行数据的聚簇索引键。

非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引。在 innodb 中有时也称非聚簇索引为二级索引或辅助索引。

总结

  • 简单来说，物理地址与逻辑地址一致，就是聚簇索引；物理地址与逻辑地址不一致，就是非聚簇索引。（比如说新华字典里，聚簇索引：拼音和偏旁部首指引到的是同一个地址；非聚簇索引：拼音可能指引到的不是那个字，可能是同音字，与偏旁部首指引到的可能不同。）
  • 索引是为了提升查询效率的一种数据结构。
  • 虽然哈希索引是 O(1)，树索引是 O(log(n))，但 SQL 有很多“有序”需求，故数据库使用树型索引
  • InnoDB 不支持哈希索引
  • 数据预读的思路是：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载更多的数据，以便未来减少磁盘 IO
  • 数据库的索引最常用 B+树：
    • 很适合磁盘存储，能够充分利用局部性原理，磁盘预读；
    • 很低的树高度，能够存储大量数据；
    • 索引本身占用的内存很小；
    • 能够很好的支持单点查询，范围查询，有序性查询；