1. 类型
- 1.1 逻辑分类
  - 1.1.1 功能分类
    - 1.1.1.1 主键索引
    - 1.1.1.2 二级索引(辅助索引)
  - 1.1.2 列数分类
- 1.2 物理分类
  - 1.2.1 聚簇索引
    - 优点：
    - 缺点：
  - 1.2.1 非聚簇索引
    - 优点：
    - 缺点：
2. 数据结构
引用：

1. 类型

1.1 逻辑分类

1.1.1 功能分类

1.1.1.1 主键索引

数据库的主键列使用的就是主键索引。

一张数据表只能有一个主键索引，并且主键不能为null，不能重复。

在mysql的InnoDB的表中，当没有显示的指定表的主键时，InnoDB会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则InnoDB将会自动创建一个6Byte的自增主键。

1.1.1.2 二级索引(辅助索引)

二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。

唯一索引，普通索引，前缀索引等索引属于二级索引。

唯一索引(Unique Key) ：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为NULL，一张表允许创建多个唯一索引。建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
普通索引(Index) ：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和NULL。
前缀索引(Prefix) ：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小，因为只取前几个字符。
全文索引(Full Text) ：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6之前只有MYISAM引擎支持全文索引，5.6之后InnoDB也支持了全文索引。

1.1.2 列数分类

单例索引：一个索引只包含一个列，一个表可以有多个单例索引。
组合索引：一个组合索引包含两个或两个以上的列。查询的时候遵循 mysql 组合索引的 “最左前缀”原则，即使用 where 时条件要按照建立索引的时候字段的排列方式放置索引才会生效。

1.2 物理分类

1.2.1 聚簇索引

聚簇索引（clustered index）不是单独的一种索引类型，而是一种数据存储方式。这种存储方式是依靠B+树来实现的，根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时，方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引放到了一块，找到索引也就找到了数据。

优点：

数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的排序查找和范围查找速度非常快

缺点：

插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键（主键列不要选没有意义的自增列，选经常查询的条件列才好，不然无法体现其主键索引性能）
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。

1.2.1 非聚簇索引

非聚集索引即索引结构和数据分开存放的索引。

优点：

更新代价比聚集索引要小。非聚集索引的更新代价就没有聚集索引那么大了，非聚集索引的叶子节点是不存放数据的

缺点：

跟聚集索引一样，非聚集索引也依赖于有序的数据
可能会二次查询(回表) :这应该是非聚集索引最大的缺点了。当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

2. 数据结构

2.1 HASH

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。
图片.png

2.2 B-TREE

B-树就是B树，多路搜索树，树高一层意味着多一次的磁盘I/O，下图是3阶B树
图片.png
B树的特征：

关键字集合分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
自动层次控制；

2.3 B+TREE

2.3.1 逻辑结构

这里我们拿数据库主键对应的B+树逻辑结构来说明，这个结构有几个关键特性：

在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。叶子节点的每一个Key指向一条记录。
非叶子节点取的是叶子节点里面Key的最小值。这意味着所有非叶子节点的Key都是冗余的叶子节点。同一层的非叶子节点也互相串联，形成了一个双向链表。

下面的结构图可以更好的说明这两个特性：
图片.png 基于这样一个数据结构以上特性就更好说明了：

范围查询：比如要查主键在[1,17]之间的记录。二次查询，先查找 1所在的叶子节点的记录位置，再查找17所在的叶子节点记录的位置（就是16所处的位置），然后顺序地从1遍历链表直到16所在的位置。
前缀匹配模糊查询：假设主键是一个字符串类型，要查询where Key like abc%，其实可以转化成一个范围查询Key in [abc,abcz]。当然，如果是后缀匹配模糊查询，或者诸如where Key like %abc%这样的中间匹配，则没有办法转化成范围查询，只能挨个遍历。
排序与分页：叶子节点天然是排序好的，支持排序和分页。

另外，基于B+树的特性，会发现对于offset这种特性，其实是用不到索引的。比如每页显示10条数据，要展示第101页，通常会写成select xxx where xxx limit 1000, 10，从offset = 1000的位置开始取10条。虽然只取了10条数据，但实际上数据库要把前面的1000条数据都遍历才能知道 offset =1000的位置在哪。对于这种情况，合理的办法是不要用offset，而是把offset = 1000的位置换算成某个max_id，然后用where 语句实现，就变成了select xxx where xxx and id > max_id limit 10，这样就可以利用B+树的特性，快速定位到max_id所在的位置，即是 offset=1000所在的位置。
[

](https://blog.csdn.net/qq_41999455/article/details/106138619)

2.3.2 物理结构

上面的树只是一个逻辑结构，最终要存储到磁盘上。下面就以 MySQL中最常用的InnoDB引擎为例，看一下如何实现B+树的存储。

对于磁盘来说，不可能一条条地读写，而都是以“块”为单位进行读写的。InnoDB默认定义的块大小是16KB，通过innodb_page_size参数指定。这里所说的“块”，是一个逻辑单位，而不是指磁盘扇区的物理块。块是InnoDB读写磁盘的基本单位，InnoDB每一次磁盘I/O，读取的都是 16KB的整数倍的数据。无论叶子节点，还是非叶子节点，都会装在 Page里。InnoDB为每个Page赋予一个全局的32位的编号，所以InnoDB 的存储容量的上限是64TB（2^32×16KB）。

16KB是一个什么概念呢？如果用来装非叶子节点，一个Page大概可以装1000个Key（16K，假设Key是64位整数，8个字节，再加上各种其他字段），意味着B+树有1000个分叉；如果用来装叶子节点，一个 Page大概可以装200条记录（记录和索引放在一起存储，假设一条记录大概100个字节）。基于这种估算，一个三层的B+树可以存储多少数据量呢？如图下图所示：
图片.png

注意：MySQL并不是从一开始就分配好这么多文件，是由树一点点慢慢增长生成

第一层：一个节点是一个Page，里面存放了1000个Key，对应1000 个分叉。
第二层：1000个节点，1000个Page，每个Page里面装1000个Key。
第三层：1000×1000个节点（Page），每个Page里面装200条记录，即是1000×1000×200 =2亿条记录，总容量是16KB×1000×1000，约16GB。

把第一层和第二层的索引全装入内存里，即（1+1000）×16KB，也即约16MB的内存。三层B+树就可以支撑2亿条记录，并且一次基于主键的等值查询，只需要一次I/O（读取叶子节点）。由此可见B+树的强大！
基于Page，最终整个B+树的物理存储类似下图所示：
图片.png
Page与Page之间组成双向链表，每一个Page头部有两个关键字段： 前一个Page的编号，后一个 Page 的编号。Page 里面存储一条条的记录，记录之间用单向链表串联，最终所有的记录形成上面所示的双向链表的逻辑结构。对于记录来说，定位到了Page，也就定位到了Page里面的记录。因为Page会一次性读入内存，同一个Page里面的记录可以在内存中顺序查找。
[