索引

在数据库中，索引可以理解为是一种单独的，物理的对数据库表中的一列或者多列的值进行排序的一种存储结构。它的作用是能让我们快速检索到想要的数据，好比字典的目录，通过目录的页码能快速找到我们想查找的内容。

在大数据量的数据库表中检索数据，如果没有建立索引，那就得全表扫描，将所有记录一一取出，与查询条件对比，然后返回满足条件的记录，大量的 IO 操作，这无疑是很耗费时间的。如果建立了索引，就能通过索引值快速定位到一个小范围的数据区间，避免全表扫描，大大提高了查询效率。

一个系统的性能好坏，系统架构和代码逻辑是一方面，还有一个点就是 SQL 语句和表索引的优化了，那首先得弄清楚索引的原理，才能进行写出更好的 SQL 以及优化，下面主要通过 MYSQL 的索引进行讲解。

树相关数据结构

其实在不同的数据库中，索引的具体实现是可能不同的，不能一口咬定索引的本质就是某某数据结构。比如 MongoDB 的索引使用的是 B-tree 数据结构；Mysql 的索引使用的是 B+tree 数据结构；再比如 ES 的倒排索引，HBase 的分布式索引等更复杂。不同的索引种类就是为了解决不同场景下的问题而设计的。

不过大部分的数据库的索引结构是树，二叉树，B 树，B+树等，下面我们简单了解下这些数据结构。

树（Tree）

树是一种数据结构，它是由 n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1. 每个结点有零个或多个子结点；

2. 没有父结点的节点称为根结点；

3. 每一个非根结点有且只有一个父结点；

4. 除了根结点外，每个子结点可以分为多个不相交的子树；

二叉树（Binary tree）

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树是指树中节点的度不大于 2 的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。它的时间复杂度是 O(n)。

当然，二叉树根据一些特性，又可以分为平衡二叉树，二叉查找树，满二叉树，完全二叉树等，此就不细讲了，大家可自行百度了解。

这里需要讲下平衡树(Balance Tree，BT) ，它指的是任意节点的子树的高度差都小于等于 1。常见的符合平衡树的有，B 树（多路平衡搜索树）、AVL 树（二叉平衡搜索树）等

B 树（B-tree）

B 树属于多叉树，又名平衡多路查找树（查找路径不只两个）。它能够保证数据有序，还保证了在查找、插入、删除等操作时性能都能保持在 O(logn)，为大块数据的读写操作做了优化。它有以下特点：

1. 任意非叶子结点最多只有 M 个子树，且 M>2

2. 根结点至少有 2 个子树

3. 除根结点以外的非叶子结点的儿子数为[M/2, M]

4. 每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；

5. 非叶子结点的关键字个数=指向子树的指针个数-1

6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且 K[i] < K[i+1]

7. 非叶子结点的指针：P[1], P[2], …, P[M]，其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于(K[i-1], K[i])的子树

8. 所有叶子结点位于同一层

在 B 树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字 K1,…,Kn 查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在 Ki 与 Ki+1 之间，Pi 为指向子树根节点的指针，此时取指针 Pi 所指的结点继续查找，直至找到，或指针 Pi 为空时查找失败。树高一层意味着多一次的磁盘 I/O。

下图是 M=3 时，一种 B 树展现形式：

B+树（B+Tree）

B+树是 B 树的一个升级版，相对于 B 树来说 B+树更充分的利用了节点的空间，B+树的特点是能够保持数据稳定有序，让查询速度更加稳定，其速度完全接近于二分法查找，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

B+树的特点如下：

1. 非叶子节点不保存关键字记录的指针，只进行数据索引。所有数据记录节点按照键值的大小存放在同一层的叶子节点上，非叶子结点只存储 key 的信息，这样使得 B+树每个非叶子节点所能保存的关键字大大增加，树的层级更少查询数据更快。

2. 叶子节点的关键字有序排列，左边结尾数据都会保存右边节点开始数据的指针。在查询大小区间的数据时候很方便，数据紧密性很高。

3. 能够保持数据稳定有序，让查询速度更加稳定，其速度完全接近于二分法查找，其插入与修改拥有较稳定的对数时间复杂度。

4. 叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样。

5. 非叶子节点的子节点数=关键字数。

6. 遍历全节点数据只需要遍历所有叶子节点即可，这有利于数据库做全表扫描。

7. 所有关键字都出现在叶子结点的链表中（稠密索引），非叶子结点相当于是叶子结点的索引（稀疏索引）。

虽然 B+树相对于 B 树有许多优势，但如果经常访问的数据离根节点很近，而 B 树的非叶子节点本身存有关键字记录数据的指针，所以 B 树对于这种数据检索的速度会要比 B+树快。

B+树的结构如下图所示：

Mysql 聚簇索引

我们知道，Mysql 的 InnoDB 使用的是 B+树存储数据，除了主键索引为聚簇索引，其它索引均为非聚簇索引。一个表中只能存在一个聚簇索引（主键索引），但可以存在多个非聚簇索引（非主键索引）。B+树中叶子节点包含数据表中的行记录，即包含主键索引和数据，这就是聚簇索引。

Mysql 存储的数据是以数据页为最小单位的，数据在数据页中是连续存储的，InnoDB 的数据文件（.idb）按主键聚集，所以 InnoDB 必须有主键，如果没有显示指定主键，则选取首个为唯一且非空的列作为主键索引，如果也没有，则 Mysql 自动为 InnoDB 表生成一个隐含字段 ROW_ID 作为主键，这个字段长度为 6 个字节，类型为长整形。数据页和数据页之间是通过双向链表来关联的，数据与数据之间通过单向链表来关联。

注意，上图数据页的行记录数据中，为简便才列出出 3 个字段 id，name 和 age，实际根据你一条数据有多少字段，就会存多少个字段的值。

你是否发现上图中有个特点，就是叶子节点的父节点，存储的数据其实是主键和数据页，到了这一层，我们通过主键比较，就能定位到具体的数据页了。但如果数据表数据量非常大了，从而数据页的数量也变得非常多，也就导致了索引页会变得很大，那我们在一个很大的索引页中再进行查找，那效率也会变得很低了。

所以针对此弊端，产生了一种新的存储结构，即索引页，如上图的第一层，它是对索引页的索引，也叫辅助索引（稀疏索引）。

假设现在需要查找 id=12 的数据，首先在最上层的索引页 1 中，通过二分查找主键，发现应该在索引页 2 中查找，然后定位到索引页 2 中，此时索引页 2 中是有记录具体的数据页了，最后通过比较主键定位到数据页 2 中，然后遍历数据页 2 中的数据即可。

可能有人会问那上一层索引页（例如索引页 1）数据量又太大了呢？毫无疑问，可以再将索引页 1 继续分裂，然后往上再构建一层，以此类推。学习过跳表的同学可能对这种数据结构理解起来很容易，它们很相似。Mysql 的 InnoDB 底层使用的就是这种数据页加索引页的结构来存储数据的。

根据以上分析，Mysql 选择 InnoDB 引擎的时候，主键尽量定义简单，不要太大，因为在主键索引中会在 B+树各层中存储主键值，会占用空间。其二尽量选择有单调性的字段作为主键，不然为了维护一个有序 B+树，非单调性的字段计算起来比较麻烦复杂，所以使用自增字段作为主键则是一个很好的选择。

Mysql 非聚簇索引

我们已经了解到主键索引（聚簇索引）的底层原理了。那我们平常建立的索引除了主键索引，肯定会还有其他非聚簇索引，例如基于 name+age 建立的索引。它又是怎么构建索引结构的呢？

其实原理同主键索引差不多，主键索引是根据主键来维护一个 B+树，非主键索引就是根据索引列来维护一个 B+树。不同的索引对应一个 B+树，索引也占用存储空间，这也就是不能建太多索引的原因。

非主键索引，会根据索引列维护一个 B+树，和主键索引不同的是，索引页中用非主键索引列（例如 name+age）代替主键，并且叶子节点的数据页存放的数据不再是整个行记录数据，而是主键加非索引列的值，例如 id+name+age。

那对于非主键索引，又是如何维护一个 B+树的呢？其实在插入数据的时候，首先会根据 name 进行排序，如果 name 值一样，再根据 age 排序，如果 age 值也一样，最后根据主键来排序，最终插入到合适的数据页中。

为什么非聚簇索引的 B+树的数据页不存放整个行记录呢？因为聚簇索引的 B+树中的数据页已经存放了整个行记录了，如果还在其他非聚簇索引中存放整个行记录，特别是一行记录的字段非常多的时候，会导致数据重复存储，严重浪费存储空间。

假如有以下查询语句（已建立 name+age 索引），需要返回行记录的全部字段信息，但是非聚簇索引中数据页只存储了 id+name+age，那其他字段的信息去哪里取呢？

SELECT * FROM person WHERE name='Mr.nobody' AND age=18

那就涉及到回表查询了。通过非聚簇索引查询到了记录主键值，然后再根据主键值再到聚簇索引中查找，就能查询到所有字段信息了，这就是回表。

那 SQL 查询条件字段是非聚簇索引的，是否就一定要进行回表查询呢？请看如下 SQL 查询语句：

SELECT id,name,age FROM person WHERE name='Mr.nobody' AND age=18

你会发现返回的字段其实都在非聚簇索引的数据页中，所以这种情况是不需要回表的。所以当在非聚簇索引中查询到的结果满足不了返回的字段时，才需要根据主键值到聚簇索引当中回表查询需要的字段。

所以我们在写 SQL 查询的时候，如果能根据主键查询到我们想要的数据，就优先使用主键查询；还有，在使用非聚簇索引查询数据的时候，需要返回的字段信息包括在非聚簇索引字段中，就直接写返回的字段，而不是写*号返回全部的字段信息，因为可能会进行回表查询增加查询时间，而且返回的数据量太大还会浪费带宽。

MyISAM 索引

上面我们是基于 InnoDB 存储引擎讲解的索引，那对于 Mysql 的另外一种存储引擎 MyISAM，索引结构又是什么样的呢？

MyISAM 存储引擎也是使用 B+树作为索引结构，和 InnoDB 的一样，但是 MyISAM 中，叶子节点的 data 域存放的是数据记录的地址，表数据存储在独立的地方。即主键索引和非主键索引叶子节点中，都不存储真正的表数据，而是存储指向表数据的地址。所以也不存在回表查询的情况。

在 MyISAM 中，主键索引和非主键索引在结构上没有任何区别，只是主键索引要求 key 是唯一的，而非主键索引的 key 可以重复。MyISAM 的索引方式也叫做非聚簇索引，这样叫是为了与 InnoDB 的聚簇索引区分。

索引存储文件

索引是存储在文件系统中的，是实际占据物理空间的，在不同的存储引擎中，索引存储的文件也不同。存储引擎是基于表的。如下创建 2 张表，一张基于 InnoDB 存储引擎，一张基于 MyISAM 存储引擎。

CREATE TABLE innodb_table (	id INT PRIMARY KEY,	name VARCHAR(20)) ENGINE=INNODB;
CREATE TABLE myisam_table (	id INT PRIMARY KEY,	name VARCHAR(20)) ENGINE=MYISAM;	

注意，以上是基于 Mysql8.020 版本，不同的 Mysql 版本可能生成的文件不一样。创建完表后，会自动生成以上文件，在 InnoDB 中，每一个表的索引(B+树)的非叶子节点存储索引，叶子节点存储索引和索引对应的数据，.ibd 文件存储着表数据和索引。而在 MyISAM 中，索引和数据是分开存储的，.MYD 文件用于存储表数据，*.MYI 文件存储索引相关的数据。