MySQL——索引底层

索引

索引是存储引擎用于快速获取数据的一种数据结构，目的是减少磁盘I/O次数，提高数据库性能。

索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同。

频繁作为查询条件（不包括唯一性太差的字段，如男女）的字段应该创建索引。

代价

1、额外的磁盘占用

2、对表进行DML（增删改）操作后，需要对索引进行维护。真正对服务器造成压力的是查询操作。

索引的种类

1、主键索引（聚簇索引）（特殊的唯一索引，增加了NOT NULL的约束）

ALTER TABLE table2 ADD PRIMARY KEY (id);

2、唯一索引（UNIQUE）

表中有primary key后不能用unique index

CREATE UNIQUE INDEX id_index on table2 (id);
ALTER TABLE table2 ADD UNIQUE id_index (id);

3、普通索引（二级索引）（最多）

ALTER TABLE table2 ADD INDEX id_index (id);

数据存储（InnoDB）

底层理解主键索引（聚簇索引/B+树）

InnoDB存储引擎将一张表的数据划分为若干个InnoDB数据页，以InnoDB数据页作为磁盘和内存之间交互的最小单位：

InnoDB数据页有自己的存储格式，实际存储的数据按照指定的行格式存储在User Records部分：

InnoDB数据页的默认大小为16KB，在一个数据页中，用户记录是按照主键由小到大的顺序串联而成的单向链表。每一个数据页中，InnoDB会自动添加两条伪记录，分别是Infimum最小记录和Supremum最大记录：

InnoDB将一个数据页中的所有记录分成若干个小组，Infimum伪记录单独分成1组，Supremum伪记录所在的分组记录条数只能在1_{8之间，其余分组记录条数只能在4}8之间。每个小组选出组内主键值最大的一条记录作为小组长，小组长添加一个属性记录组员个数（包括自己），并把小组长的地址取出编成目录（槽），槽在物理空间上是连续的，意味着很容易找到它的上一个和下一个，所以可以用二分查找对槽进行快速查找从而定位到具体的某个记录：

但是记录之间是单向链表，无法向前追溯，所以需要找到上一个槽，定位到上一个槽所指向的小组长，进而向后遍历找到目标主键的记录：

虽然在一个数据页内能够轻松地快速查询，但是页号如何快速确定呢？各个数据页在逻辑上使用双向链表的方式进行连接：

因此给上述数据页添加一个目录，该目录中的一条记录（称为目录项记录）对应一个数据页，这个目录称为存储目录项的数据页。目录项记录记录了对应数据页中的最小主键值和数据页号：

所以整个查询流程是这样：先找存储目录项的数据页（目录），对该目录使用二分法快速定位目录项记录，进而根据数据页号定位到数据页，再对查到的数据页进行二分查找，找到目标主键的目录。

存储目录项的数据页（目录）多了则再为目录生成一个目录。

这就是B+树，即索引。树的叶子结点存储了完整的用户记录，所以说索引即数据，数据即索引。

底层理解普通索引

没有主键，InnoDB也会选取Unique键作为主键，Unique键也没有，就会自动为每个记录添加DB_ROW_ID的列作为默认主键，所以主键索引一定是存在的。

普通索引（以name索引举例）：

根据name字段快速找到主键，再根据主键查找用户记录。

叶子结点不再存放完整的用户记录，而是只记录name列和主键列。其次，InnoDB数据页中存放的用户记录和目录项记录变为按照name列排序。（目录项记录除了存储name列和页号之外，为什么还要存储主键值？是为了在搜索条件刚好在目录项记录中的情况下直接返回主键值）

（创建表时可以对字符串字段指定字符集和比较规则）

得到主键ID后，根据主键ID到主键索引中查找完整的用户记录。此过程称为回表

若没有为name列设置唯一性约束，那么很有可能会找到多个符合条件的主键ID，就需要多次回表。