8.1 InnoDB页

InnoDB 采取的方式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB中页的大小一般为 16 KB。也就是在一般情况下，一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。

8.2 InnoDB行格式

我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB 存储引擎到现在为止设计了4种不同类型的行格式，分别是 Compact 、 Redundant 、Dynamic 和 Compressed 行格式，随着时间的推移，可能会设计出更多的行格式，但是不管怎么变，在原理上大体都是相同的。

CREATE TABLE record_format_demo ( 
        c1 VARCHAR(10), 
        c2 VARCHAR(10) NOT NULL, 
        c3 CHAR(10), 
        c4 VARCHAR(10) 
) CHARSET=ascii ROW_FORMAT=COMPACT; // 指定字符集和行格式

8.3 无索引查找

各个数据页可以组成一个 双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个 单向链表，每个数据页都会为存储在它里边儿的记录生成一个 页目录，在通过主键查找某条记录的时候可以在 页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

8.3.1 一个页中查找

以主键为搜索条件

这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应
分组中的记录即可快速找到指定的记录。

以其他列为搜索条件

对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的 页目录，所以
我们无法通过二分法快速定位相应的 槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，
然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

8.3.2 在很多页中查找

定位到记录所在的页。
从所在的页内中查找相应的记录。

在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。

8.4 索引

新建一个表：

CREATE TABLE index_demo( 
    c1 INT, 
    c2 INT, 
    c3 CHAR(1), 
    PRIMARY KEY(c1) 
) ROW_FORMAT = Compact;

行格式示意图：

record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 我们还没用过，等会再说～
next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。
各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。
其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

把一些记录放到页里边的示意图就是：

8.4.1 一个简单的索引方案

我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有
规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们
想快速的定位到需要查找的记录在哪些数据页中该咋办？还记得我们为根据主键值快速定位一条记录在页中的位
置而设立的页目录么？我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录，建这个目录必须完
成下边这些事儿：

下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向 index_demo 表插入3条记录，这些记录已经按照主键值的大小串联成一个单向链表

从图中可以看出来， index_demo 表中的3条记录都被插入到了编号为 10 的数据页中了。此时我们再来插入
一条记录，因为页10 最多只能放3条记录，所以我们不得不再分配一个新页：

新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。另外，页10 中用户记录最大的主键值是 5 ，而页28 中有一条记录的主键值是 4 ，因为 5 > 4 ，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为 4 的记录的时候需要伴随着一次记录移动，也就是把主键值为 5 的记录移动到页28 中，然后再把主键值为 4 的记录插入到页10 中，这个过程的示意图如下：

这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为 页分裂 。

由于数据页的编号可能并不是连续的，所以在向 index_demo 表中插入许多条记录后，可能是这样的效果：

因为这些 16KB 的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

页的用户记录中最小的主键值，我们用 key 来表示。
页号，我们用 page_no 表示。

所以我们为上边几个页做好的目录就像这样子：

这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为 20 的记录，具体查找过程分两步：

先从目录项中根据二分法快速确定出主键值为 20 的记录在目录项3 中（因为 12 < 20 < 209 ），它对应的页是页9 。
再根据前边说的在页中查找记录的方式去页9 中定位具体的记录。

这个简单的目录就叫索引

8.4.2 InnoDB中的索引方案

需要一种可以灵活管理所有目录项的方式。他们灵光乍现，忽然发现这些目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。那 InnoDB 怎么区分一条记录是普通的用户记录还是目录项记录呢？别忘了记录头信息里的record_type 属性，它的各个取值代表的意思如下：

0 ：普通的用户记录
1 ：目录项记录
2 ：最小记录
3 ：最大记录

先到存储目录项记录的页，也就是页 30 中通过二分法快速定位到对应目录项，因为 12 < 20 < 209 ，所以定位到对应的记录所在的页就是页9 。
再到存储用户记录的页9 中根据二分法快速定位到主键值为 20 的用户记录。

虽然说 目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有 16KB 大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，该咋办呢？当然是再多整一个存储目录项记录的页。

确定目录项记录页
我们现在的存储目录项记录的页有两个，即页30 和页32 ，又因为页30 表示的目录项的主键值的范围是[1, 320) ，页32 表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在页30 中。
通过目录项记录页确定用户记录真实所在的页。
在真实存储用户记录的页中定位到具体的记录。

不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到 B+ 树这个数据结构中了，所以我们也称这些数据页为节点。从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点 ，其余用来存放目录项的节点称为非叶子节点或者内节点 ，其中 B+ 树最上边的那个节点也称为根节点。
一般情况下，我们用到的 B+ 树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页）

8.4.3 聚簇索引

我们上边介绍的 B+ 树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照主键的大小顺序排成一个单向链表。各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+ 树的叶子节点存储的是完整的用户记录。
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

我们把具有这两种特性的 B+ 树称为聚簇索引 ，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引 并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建（后边会介绍索引相关的语句），InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在 InnoDB 存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

8.4.4 建立索引

InnoDB 和 MyISAM 会自动为主键或者声明为 UNIQUE 的列去自动建立 B+ 树索引，但是如果我们想为其他的列建立索引就需要我们显式的去指明。

// 表创建时建立索引
CREATE TABLE index_demo( 
   c1 INT, 
   c2 INT, 
   c3 CHAR(1), 
   PRIMARY KEY(c1), 
   [KEY | INDEX] idx_c2_c3 (c2, c3) // key 和 index 是同义词，任意选用一个就行
);
// 修改表结构添加索引
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);
// 修改表结构删除索引
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

8.5 索引适用条件

CREATE TABLE person_info( 
   id INT NOT NULL auto_increment, 
   name VARCHAR(100) NOT NULL, 
   birthday DATE NOT NULL, 
   phone_number CHAR(11) NOT NULL, 
   country varchar(100) NOT NULL, 
   PRIMARY KEY (id), 
   KEY idx_name_birthday_phone_number (name, birthday, phone_number) 
);

先按照name 列的值进行排序。
如果name 列的值相同，则按照birthday 列的值进行排序。
如果birthday 列的值也相同，则按照phone_number 的值进行排序。

都以建立索引的字段顺序来匹配

8.5.1 全值匹配

8.5.2 匹配左边的列

8.5.3 匹配列前缀

8.5.4 匹配范围值

8.5.5 精确匹配某一列并范围匹配另外一列

8.5.6 用于排序

8.5.7 用于分组

8.6 挑选索引

8.6.1 只为用于搜索、排序或分组的列创建索引

只为出现在 WHERE 子句中的列、连接子句中的连接列，或者出现在 ORDER BY 或 GROUP BY 子句中的列创建索引。而出现在查询列表中的列就没必要建立索引。

8.6.2 考虑列的基数

列的基数指的是某一列中不重复数据的个数，比方说某个列包含值 2, 5, 8, 2, 5, 8, 2, 5, 8 ，虽然有 9 条记录，但该列的基数却是 3 。也就是说，在记录行数一定的情况下，列的基数越大，该列中的值越分散，列的基数越小，该列中的值越集中。这个列的基数指标非常重要，直接影响我们是否能有效的利用索引。假设某个列的基数为 1 ，也就是所有记录在该列中的值都一样，那为该列建立索引是没有用的，因为所有值都一样就无法排序，无法进行快速查找了～而且如果某个建立了二级索引的列的重复值特别多，那么使用这个二级索引查出的记录还可能要做回表操作，这样性能损耗就更大了。所以结论就是：最好为那些列的基数大的列建立索引，为基数太小列的建立索引效果可能不好。

8.6.3 索引列的类型尽量小

我们在定义表结构的时候要显式的指定列的类型，以整数类型为例，有 TINYINT 、 MEDIUMINT 、 INT 、 BIGINT 这么几种，它们占用的存储空间依次递增，我们这里所说的类型大小指的就是该类型表示的数据范围的大小。能表示的整数范围当然也是依次递增，如果我们想要对某个整数列建立索引的话，在表示的整数范围允许的情况下，尽量让索引列使用较小的类型，比如我们能使用 INT 就不要使用 BIGINT ，能使用 MEDIUMINT 就不要使用INT ～这是因为：

数据类型越小，在查询时进行的比较操作越快（这是CPU层次的东东）
数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以放下更多的记录，从而减少磁盘 I/O 带来的性能损耗，也就意味着可以把更多的数据页缓存在内存中，从而加快读写效率。

这个建议对于表的主键来说更加适用，因为不仅是聚簇索引中会存储主键值，其他所有的二级索引的节点处都会存储一份记录的主键值，如果主键适用更小的数据类型，也就意味着节省更多的存储空间和更高效的 I/O 。

8.6.4 索引字符串值的前缀

索引列的字符串前缀其实也是排好序的，所以索引的设计者提出了个方案 —- 只对字符串的前几个字符进行索引也就是说在二级索引的记录中只保留字符串前几个字符。这样在查找记录时虽然不能精确的定位到记录的位置，但是能定位到相应前缀所在的位置，然后根据前缀相同的记录的主键值回表查询完整的字符串值，再对比就好。

CREATE TABLE person_info( 
   name VARCHAR(100) NOT NULL, 
   birthday DATE NOT NULL, 
   phone_number CHAR(11) NOT NULL, 
   country varchar(100) NOT NULL, 
   KEY idx_name_birthday_phone_number (name(10), birthday, phone_number) 
);

name(10) 就表示在建立的 B+ 树索引中只保留记录的前 10 个字符的编码，这种只保留索引字符串值的前缀的策略是我们非常鼓励的，尤其是在字符串类型能存储的字符比较多的时候。

8.6.5 让索引在比较表达式中单独出现

WHERE my_col * 2 < 4
WHERE my_col < 4/2

第1个 WHERE 子句中 my_col 列并不是以单独列的形式出现的，而是以 my_col * 2 这样的表达式的形式出现的，存储引擎会依次遍历所有的记录，计算这个表达式的值是不是小于 4 ，所以这种情况下是使用不到为 my_col 列建立的 B+ 树索引的。而第2个 WHERE 子句中 my_col 列并是以单独列的形式出现的，这样的情况可以直接使用 B+ 树索引。
所以结论就是：如果索引列在比较表达式中不是以单独列的形式出现，而是以某个表达式，或者函数调用形式出现的话，是用不到索引的。

8.4.6 主键插入顺序

8.4.7 冗余和重复索引

通过 idx_name_birthday_phone_number 索引就可以对 name 列进行快速搜索，再创建一个专门针对 name 列的索引就算是一个冗余索引，维护这个索引只会增加维护的成本，并不会对搜索有什么好处。

CREATE TABLE person_info( 
   id INT UNSIGNED NOT NULL AUTO_INCREMENT, 
   name VARCHAR(100) NOT NULL, 
   birthday DATE NOT NULL, 
   phone_number CHAR(11) NOT NULL, 
   country varchar(100) NOT NULL, 
   PRIMARY KEY (id), 
   KEY idx_name_birthday_phone_number (name(10), birthday, phone_number), 
   KEY idx_name (name(10)) 
);

8.7 总结

B+ 树索引在空间和时间上都有代价，所以没事儿别瞎建索引。
B+ 树索引适用于下边这些情况：
- 全值匹配
- 匹配左边的列
- 匹配范围值
- 精确匹配某一列并范围匹配另外一列
- 用于排序
- 用于分组
在使用索引时需要注意下边这些事项：
- 只为用于搜索、排序或分组的列创建索引
- 为列的基数大的列创建索引
- 索引列的类型尽量小
- 可以只对字符串值的前缀建立索引
- 只有索引列在比较表达式中单独出现才可以适用索引
- 为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT 属性。
- 定位并删除表中的重复和冗余索引
- 尽量使用覆盖索引进行查询，避免回表带来的性能损耗

8. 索引