概述

索引是用来快速检索出具有特定值的记录，它可以大大提高查询速度。如果没有索引，数据库就必须从第一条记录开始进行全表扫描来找到相关的行。数据越多，成本就越高，检索时如果表的列存在索引，那么MySQL就能快速到达指定位置去搜索数据文件，而不必查看所有数据。

索引是存储引擎快速找到记录的一种数据结构，例如 MyISAM 引擎和 Innodb 引擎都使用 B+ Tree 作为索引结构。 ——《高性能MySQL》

MySQL中索引的存储类型有两种：BTREE和HASH，具体和表的存储引擎相关；MyISAM 和 InnoDB存储引擎只支持 BTREE 索引，MEMORY/HEAP 存储引擎可以支持HASH和BTREE索引。

• BTREE 索引：BTREE 索引是一种平衡树数据结构，节点按照键值有序排列，可以快速进行范围查询和排序。
• HASH 索引：基于哈希表实现，通过哈希函数将键值映射到哈希表中的位置。

以下示例展示如何在不同存储引擎中创建 BTREE 和 HASH 索引：

sql
CREATE TABLE myisam_table (
    id INT AUTO_INCREMENT,
    name VARCHAR(100),
    PRIMARY KEY (id),
    INDEX idx_name (name)
) ENGINE=MyISAM;

CREATE TABLE innodb_table (
    id INT AUTO_INCREMENT,
    name VARCHAR(100),
    PRIMARY KEY (id),
    INDEX idx_name (name)
) ENGINE=InnoDB;

底层原理

磁盘IO耗时

磁盘读取数据，靠的是机械运动，每次读取数据花费的时间可以分成3个部分：

• 寻道时间（Seek Time）：寻道时间是磁盘臂移动到目标磁道所需的时间。主流磁盘的寻道时间一般在 5ms 以下。这是磁盘 I/O 中最耗时的部分。
• 旋转延迟（Rotational Latency）：旋转延迟是磁盘旋转到目标扇区所需的时间，通常定磁盘转速。
• 传输时间（Transfer Time）：传输时间是数据从磁盘读取到内存或从内存写入磁盘所需的时间。相对于寻道时间和旋转延迟，传输时间一般在零点几毫秒，可以忽略不计。

一次磁盘I/O的时间大约在 9ms，听起来还不错，但相比CPU指令执行时间是非常慢的。比如，计算机每秒可以执行 5 亿条指令，执行一次I/O的时间大概可以执行 40 万条指令，数据库百万级甚至千万级的数据，每次IO都用 9ms 的时间，显然和耗时。

以下是一些常见硬件操作的延迟时间对比：

• L1 缓存访问：约 1 纳秒（ns）
• L2 缓存访问：约 4 纳秒（ns）
• 主内存访问：约 100 纳秒（ns）
• 固态硬盘（SSD）访问：约 25 微秒（µs）
• 传统硬盘（HDD）访问：约 9 毫秒（ms）

从上面的数据可以看出，磁盘 I/O 的延迟时间远远高于其他硬件操作的延迟时间。

局部预读性原理

上面提到到磁盘I/O是非常高昂代价的操作，计算机系统对此也做了一些优化，当发生一次I/O时，不仅会把当前磁盘地址的数据读取到内存中，也会把相邻的数据也读取到内存缓冲区中，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快访问到。这样可以减少后续对相邻数据的磁盘 I/O 操作，提高整体性能。

每一次I/O读取的数据我们称之为一页（Page）。页（Page）是操作系统管理内存和磁盘之间数据交换的基本单位。具体一页的数据有多大，和操作系统有关，一般为4K或8K，也就是我们读取一页数据的时候，实际上才发生了一次I/O。

除此之外，数据库对数据的读取并不是以行为单位进行的，无论是读取一行还是多行，都会将该行或者多行所在的页全部加载进来，然后再读取对应的数据记录，也就是说，读取所耗费的时间与行数无关，只与页数有关。

MySQL 中所有的数据其实都是以文件的形式存储在磁盘上的，而从磁盘上随机访问对应的数据非常耗时，所以数据库程序和操作系统提供了缓冲池和内存以提高数据的访问速度。

页

MySQL 的基本存储结构是「页」，行记录是存储在页中的。

哈希索引

哈希索引通过将键值（key）通过哈希函数转换为哈希值（hash value），然后根据这个哈希值直接定位到存储位置，从而实现快速查找。其时间复杂度为 O(1)。 哈希函数是哈希索引的核心，它将输入的键值映射到一个固定范围内的哈希值。一个好的哈希函数应该具有以下特性：

• 均匀分布：不同的键值应该均匀地分布在哈希表中，避免哈希冲突。
• 效率高：计算哈希值的时间应该尽可能短。

哈希索引的优点

• 查找速度快：哈希索引的查找时间复杂度为 O(1)，非常适合快速查找特定值。
• 简单实现：哈希索引的实现相对简单，适用于等值查询。

哈希索引的缺点

• 不支持范围查询：哈希索引不适用于范围查询，因为哈希值没有顺序关系。
• 哈希冲突处理复杂：虽然有多种方法处理哈希冲突，但仍然会影响查找性能。
• 占用内存大：哈希表通常需要预留较大的空间，以减少哈希冲突的发生。

哈希索引的应用场景

• 等值查询：例如，通过主键或唯一键查找特定记录。
• 频繁的插入和删除操作：哈希索引在插入和删除操作上效率较高。

二叉查找树

二叉查找树是一种二叉树，满足以下性质：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 它的左、右子树也分别为二叉查找树。

优点： 因为二叉查找树是有序的，左孩子都比父节点小，右孩子都比父节点大，所以其查找效率很高，类似于二分查找可以达到O(logN). 缺点： 当二叉查找树的结构变成了下图右边这种结构之后，时间复杂度就会变成O(N)

操作

• 查找：从根结点开始，比较要查找的值与当前结点的值，若小于当前结点的值，则递归查找左子树；若大于当前结点的值，则递归查找右子树。
• 插入：从根结点开始，比较要插入的值与当前结点的值，若小于当前结点的值，则递归插入到左子树；若大于当前结点的值，则递归插入到右子树；直到找到一个空位置插入新结点。
• 删除：删除操作较为复杂，有三种情况：
  • 删除叶子结点：直接删除该结点。
  • 删除只有一个子结点的结点：将该结点的父结点指向其唯一的子结点。
  • 删除有两个子结点的结点：找到该结点的中序后继（右子树中最小的结点）或中序前驱（左子树中最大的结点），用后继或前驱替换该结点的值，然后递归删除后继或前驱结点。

B树

B树呢，又叫平衡多路查找树。如果每个节点最多有m个孩子，那么这样的树就是m阶B树。咱们可以看到，该图就是一个三阶B树的样子。

特征

• 节点的关键字数量：
  • 每个节点包含最多 m-1 个关键字，每个节点中的元素都按照升序排列，每个元素的左子树中的所有关键字都小于它，右子树中所有元素都大于它。
• 子节点的数量：
  • 根节点至少包括两个子节点。
  • 除了根节点和叶节点外，其他每个节点至少有Math.ceil(m/2)个子节点（对m/2向上取整，例如m为3的话就取2），最多有 m 个子节点。
• 树的高度：
  • 所有叶子节点在同一层，树的高度保持平衡。

B+树

B+树是B树的变体，其定义基本与B树相同。二者最大的不同是B+树的非叶子结点不保存数据，非叶子节点只用于索引，所有数据/记录都保存在叶子结点中。B+Tree的检索都是从根节点开始，叶子节点结束.

1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

3） m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

4）内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接

特征

• 关键字存储：
  • 有k个子树的中间节点包含k个元素。
  • 非叶子节点只存储索引，不存储实际数据。
  • 叶子节点存储所有关键字及其对应的数据记录。
  • 所有中间节点的元素都同时存在于子结点，在子结点元素中是最大或最小元素。
• 叶子节点链表：
  • 所有叶子节点通过指针连接，形成一个有序链表，方便范围查询。
• 子节点数量：
  • 每个非叶子节点最多有 m 个子节点，至少有Math.ceil(m/2)个子节点。

之所以B+树的非叶子节点选择只存储索引，叶子节点存储数据的原因是在数据库中页的大小是相对固定的（InnoDB 中页的默认大小是 16KB），如果不存储数据，那么就会存储更多的键值和指针，相应的树的阶数就会更大，树的高低会更低，我们查找数据进行磁盘的 IO 次数会再次减少，数据查询的效率也会更快。比如，假设，有一个B+ 树单节点可以存储 1000 个键值，3 层的 B+ 树可以存储 1000 × 1000 × 1000 = 10 亿 个数据。一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。

B 树和 B+ 树的区别

1. B+树中只有叶子节点会带有指向记录的指针，而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。
2. B+树中所有叶子节点都是通过指针连接在一起，而B树不会。 具体区别

• 数据存储位置：
  • B树：数据可以存储在所有节点（包括非叶子节点和叶子节点）。
  • B+树：数据仅存储在叶子节点，非叶子节点只存储索引。
• 查找效率：
  • B树：查找时可能在非叶子节点找到数据，路径可能较短。
  • B+树：查找时必须到叶子节点才能找到数据，但由于树更矮，查找效率较高，且范围查询效率更高。
• 范围查询：
  • B树：范围查询不如B+树高效，因为数据分布在所有节点中。
  • B+树：叶子节点通过链表连接，范围查询非常高效。
• 树的高度：
  • B树：由于每个节点存储数据和索引，节点能容纳的键值较少，树可能较高。
  • B+树：非叶子节点仅存储索引，能容纳更多键值，树更矮。

综上，B+树的磁盘IO成本更低，因为B+树的非叶子节点只存放索引的信息，不存放数据，可以指向更多的数据，一次性读取更多的要查找的关键字到内存中，因此相对来说IO的次数，也就降低了；B+树的查询效率更稳定，以任何数据的查找都是从根节点到叶子节点；B+Tree更利于对数据库的扫描，可以直接只在叶子节点里根据链表指针做扫描，不用每次都遍历整棵树

B+ 树的操作

插入

• 初始状态，针对空树，创建一个叶子结点，将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
• 针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中。父结点的key左孩子指针向左结点，右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
• 针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中。父结点的key左孩子指向左结点，右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

举个例子

1. 假定我们要在这样一个 B+ 树中插入 7。
2. 首先在 B+ 树中找到 7 的位置，将对应元素插入进去。

3. 当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

3. 当前结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，结果如下图所示。

4. 当前结点的关键字个数满足条件，插入结束。

删除

• 删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束，否则执行下一步。
• 若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行下一步。
• 若兄弟结点中没有多余的key，则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点，执行下一步（下一步以后的操作主要是为了更新索引结点）。
• 若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行下一步
• 若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行下一步
• 当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

举个例子

1. 假定我们要在这样一个 B+ 树中删除 7

2. 首先删掉对应叶节点中的内容

3. 当前结点关键字个数小于2，兄弟结点中的也没有富余的关键字，所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。

4. 此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。

高度

树的高度直接影响了查询的性能，一般树的高度维持在 3~4 层。

磁盘IO次数取决于B+树的高度 h。假设当前数据表的数据为 N，每个磁盘块的数据项的数量是 m，则有B+树的高度h为 h = log(m + 1)N 当数据量 N 一定的情况下，m 越大，h 越小。

密集索引和稀疏索引

密集索引

密集索引是一种索引结构，其中索引的每个键值都直接对应一条数据记录的物理位置。叶子节点不仅存储键值，还存储与该键值相关的完整数据记录。由于密集索引决定了表的物理排列顺序，一个表只能有一个物理排列顺序，所以一个表只能创建一个密集索引。在密集索引中，数据记录按索引键值的顺序存储在磁盘上。叶子节点包含了实际的数据记录或指向数据记录的指针。

稀疏索引

稀疏索引只为某些键值建立，而不是每个键值都建立索引项。在稀疏索引中，只有部分数据记录有对应的索引项，索引项之间的间隔可以是固定的或者根据需要调整。叶子节点包含键值和指向数据记录的地址或主键。查找数据时，首先通过稀疏索引定位到最近的索引项，然后通过该索引项中的地址或主键进一步查找实际的数据记录。由于不是每个数据记录都有索引项，查找过程可能需要额外的步骤来定位具体的数据记录。

InnoDB

InnoDB必须有且仅有一个密集索引，这个密集索引的选取规则如下：

• 若一个主键被定义，该主键则作为密集索引；
• 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引；
• 若不满足以上条件，InnoDB内部会生成一个隐藏主键（密集索引），这个隐藏的主键是一个6字节的列，该列的值会随着数据的插入而自增，也就是说，我们的InnoDB必须有一个主键，而该主键就必须作为唯一的密集索引而存在。
• 非主键索引通过存储键值和主键值，提高了对非主键列的查询效率，但查找过程需要两次查找：一次在非主键索引中，另一次在主键索引中。非主键索引适用于需要加速对非主键列进行查询的场景，且每个表可以有多个非主键索引

InnoDB会有一个密集索引，将主键组织到一颗B+树中，而行数据就存储在叶子节点上，因为InnoDB的主键索引和对应的数据是保存在同一个文件当中的，在检索的时候，加载叶子节点的主键进入内存的同时，也加载了对应的数据。即若使用 where id =xx 这样的条件查询主键，则按照B+树的检索算法即可查找到对应的叶子节点，并获得对应的行数据。若对稀疏索引进行条件筛选，则需要经历两个步骤，第一步，在稀疏索引的B+树中检索该键定位到主键信息，获取主键信息后还要经过第二步，第二步就是使用主键 where id =xx 在密集索引的B+树中再执行一次检索操作，最终再到达叶子节点，获取整行的数据。