索引数据结构

这儿聊得是索引的数据结构，根数据库无关，每个数据库的实现方式可能有所差异，但基本原理不变。

如图所示，叶子节点存放索引的健值（堆表）或者整行数据（IOT 表）。
非叶节点存放 Fanout（扇出），其实就是位置指针，每条箭头的起点处就是 Fanout，第一根箭头的 Fanout 表示，小于 25 的到哪儿去找。第二个 Fanout 表示 [25,50) 的到哪儿去找。指向下一层节点的指针的数量就是 Fanout 数量。B+ 树在高度不高的情况下，扇出数却很多，意味着可以索引大量的叶子节点。

在上图的基础之上，我们想插入 95，最后一个叶子节点已经满了，所以只能分裂，从中间值 85 进行分裂，将 85 往上提，此时，第二层也满了，第二层以中间值 60 进行分裂，最终结果如下图所示：

分裂有很多方法，不见得是以中间为准进行分裂，这儿只是一个范例。

从上面分裂的例子可以看见，叶子节点的分裂 (split) 实现起来比较复杂，树的高度可能发生变化，且伴随着锁。可见，Insert 操作的开销是很大的，所以，在 MySQL 中索引块的 Fill Factor(类似 Oracle 的 PCT FREE) 一般设置较低(如 50%)，以空间换时间。

在上图的基础上，删除70和25后：

删除60后，发生索引块合并：

注意到叶子节点之间是有双向链存在的，叶子节点通过双向链做了排序，这样，在范围查找时就能派上用场。所有排序都是逻辑排序（用指针保证逻辑上有序），不是物理的。

考点：
1）叶块之间使用双向链连接。
2）删除表行时索引叶块也会更新，但只是逻辑更改，并不做物理的删除叶块。
3）索引叶块中不保存表行键值的 null 信息（即常说的索引不存空值）。

为什么通过索引检索数据快

索引之所以检索数据快，是因为索引高度低，但其扇出数量大，即可以指向很多的叶子节点。可以把索引理解为一个小表。

为了简单起见，我们按页使用率 100% 来计算（但实际中，一个页中只有70%的空间是使用到的，我们还要考虑页头开销，索引碎片，预留空间等）。

在 MySQL 中，IOT 表的叶子节点存放的是完整的记录，通过如下命令我们可以知道每行的平均长度，据此我们可以大致计算每个叶子节点能够存放的记录数：

mysql> show table status like employees;  <-- avg_row_length 表示表的平均行长度

非叶节点记录的是(key,指针)，一个扇出(指针)我们一般计算为6字节，据此我们可以大致计算出一个非叶节点可以指向多少个叶子节点。

通过这样的计算，我们可以直观地感受到索引扇出数量大，高度低的特性。

高度为3的索引，假如要读三个页，需要多少时间？假如IOPS是100，则需要 3/100 = 0.03s 秒，有些公司把慢查询设置为 0.5s 的原因也就在这儿，读一个块的时间是0.01s，0.5s 表示至少发生了50个块的IO，但是这还是有点儿问题，它没有考虑到范围查询，ORDER BY，JOIN 等因素。

现在的存储 IOPS 能力，再差也能达到 100 IOPS，SSD 再差能达到 10000 IOPS，基本上能达到 50000 IOPS 。

索引数据查找算法

MySQL 在 B+ 树索引中检索数据使用的是 binary search (二分查找法，又称折半检索)，简单地说，就是先看中间，找到就返回，如果没找到，小于找左边，大于找右边，依此递归。在叶子节点中找数据也是用的二分查找法。

例如，(20, 40, 25, 63, 28, 72, 46, 90, 54, 30)，需要找到 90：

(20, 40, 25, 63, 28, 72, 46, 90, 54, 30)
第一步找到72          ^
第二步找到54                      ^    
第三步找到90                  ^                    

就上面这个例子，查找所有元素，

顺序查找法的平均代价是：
(1+2+3+4+5+6+7+8+9+10)/10=5.5

二分查找法的平均代价是：
(4+3+2+4+3+1+4+3+2+3)/10=2.9

索引的分类

MySQL 中除了 B+ 树索引，还有全文索引、R树索引、T树索引、Hash索引。

我们经常把索引比作目录，其实就是在说 B树 或者 B+树 索引，我们打交道的 90% 以上都是 B树 或者 B+树索引。

B+ TREE INDEX IN INNODB(IOT)

• Clustered Index(聚集索引): Leaf page store all row data
• Secondary Index(非聚集索引，二级索引): Leaf page store key & primary key info
  Bookmark lookup(书签查找，即回表)，找到索引 key 对应的主键后，再到聚集索引去查找，注意，回表并不是只多一次 IO，若聚集索引的高度为 N，则要多 N 次 IO。

IOT表的 页内，页与页之间 都是逻辑有序的。对于IOT表，只要主键不更新（一般也不会更新），索引就不会更新，对 UPDATE 比较友好。

B+ TREE INDEX IN MYISAM(Heap Table)

• All index is non-clustered/ secondary Index

创建/重建索引

MySQL 有两种方法创建索引：

mysql> alter table xxx add index yyy (col1,col2)[, algorithm=INPLACE, lock=NONE];
mysql> create index  yyy on xxx (col1,col2) [algorithm=INPLACE lock=NONE];

ALGORITHM and LOCK clauses may be given to influence the table copying method and level of concurrency for reading and writing the table while its indexes are being modified. They have the same meaning as for the ALTER TABLE statement. For more information, see Section 13.1.8, “ALTER TABLE Statement”.

Concurrency Control(LOCK)

For ALTER TABLE operations that support it, you can use the LOCK clause to control the level of concurrent reads and writes on a table while it is being altered. Specifying a non-default value for this clause enables you to require a certain amount of concurrent access or exclusivity during the alter operation, and halts the operation if the requested degree of locking is not available. The parameters for the LOCK clause are:

• LOCK = DEFAULT
  Maximum level of concurrency for the given ALGORITHM clause (if any) and ALTER TABLE operation: Permit concurrent reads and writes if supported. If not, permit concurrent reads if supported. If not, enforce exclusive access.
• LOCK = NONE
  If supported, permit concurrent reads and writes. Otherwise, an error occurs.
• LOCK = SHARED
  If supported, permit concurrent reads but block writes. Writes are blocked even if concurrent writes are supported by the storage engine for the given ALGORITHM clause (if any) and ALTER TABLE operation. If concurrent reads are not supported, an error occurs.
• LOCK = EXCLUSIVE
  Enforce exclusive access. This is done even if concurrent reads/writes are supported by the storage engine for the given ALGORITHM clause (if any) and ALTER TABLE operation.

Copying method(ALGORITHM)

ALTER TABLE operations are processed using one of the following algorithms:

COPY: Operations are performed on a copy of the original table, and table data is copied from the original table to the new table row by row. Concurrent DML is not permitted.

INPLACE: Operations avoid copying table data but may rebuild the table in place. An exclusive metadata lock on the table may be taken briefly during preparation and execution phases of the operation. Typically, concurrent DML is supported.

The ALGORITHM clause is optional. If the ALGORITHM clause is omitted, MySQL uses ALGORITHM=INPLACE for storage engines and ALTER TABLE clauses that support it. Otherwise, ALGORITHM=COPY is used.

Specifying an ALGORITHM clause requires the operation to use the specified algorithm for clauses and storage engines that support it, or fail with an error otherwise. Specifying ALGORITHM=DEFAULT is the same as omitting the ALGORITHM clause.

查看表上的索引

在 MySQL 中，可以通过如下方法来查看一个表列上的索引：

• desc table <--- 看 key 列
• show create table
• show index from table
• query on information_schema.STATISTICS

索引列的可选性

在查看 MySQL 的索引信息时，cardinality 表示该列上不重复值的数量，是一个预估值（采样得到），还是比较准确的，来源于 information_schema.STATISTICS 表的 CARDINALITY 字段。

对于组合索引（compund index），seq_in_index 表示列在索引中的顺序，第一个列的 cardinality 表示本列不重复值的数量，第二个列的 cardinality 表示两个列组合起来不重复值的数量。

可以通过如下查询来统计表上的索引及其 cardinality、总行数。

SELECT t.TABLE_SCHEMA,t.TABLE_NAME,INDEX_NAME, CARDINALITY, TABLE_ROWS, CARDINALITY/TABLE_ROWS AS SELECTIVITY
FROM TABLES t, (
select table_schema, table_name, index_name, cardinality
from STATISTICS
where (table_schema , table_name, index_name, seq_in_index) in (
    select table_schema, table_name, index_name,max(seq_in_index)
    from STATISTICS
    group by table_schema , table_name , index_name
)
) s
WHERE
t.table_schema = s.table_schema
AND t.table_name = s.table_name
ORDER BY SELECTIVITY;

复合索引的 cardinality 应该看 max(seq_in_index) 的值。最内层子查询查询出表名、索引名及其 max(seq_in_index)，第二层子查询查询出表名、索引名及其 cardinality，最外层子查询通过与 tables 作关联，查询出表名、索引名、表行数、cardinality 与行数的比值来判断该索引是否有必要。

通过最后一列的 SELECTIVITY 是否接近1，判断该索引创建是否合理。推荐 SELECTIVITY 15% 以上是适合的。需要注意的是 Cardinality 和 table_rows 的值，都是通过随机采样，预估得到的。

注意：MySQL5.6 的版本 STATISTICS 数据存在问题 ，截止 5.6.28 仍然存在，官方定性为 Bug。可以从 mysql.innodb_index_stats 去取数据。

MySQL 查看索引是否合理

mysql> select * from x$schema_index_statistics

结合之前的 SELECTIVITY 和这里的数值，可以更好的判断索引是否合理。注意，重启后视图数据归 0。

MySQL 什么时候会用上索引

对于 (a,b)， (a,b)和(a)是排序过的，b没有排序
所以 where a=? 和 where a=? and b=? 都会使用索引
但是 where b=? 就不能使用索引

如果是 select * from xxx where a=? or b=? 会使用到索引吗？不会

三个列的组合索引
(a,b,c)

a=? 可以
a=? and b=? and c=? 可以
select * from xxx where b=? and c=? 用不上

select * from a=? and c=? 可以，通过 a 走索引，通过c过滤

(user_id,buy_date)
select count(1) from xxx where buy_date>='2011-01-01' and buy_date<='2012-01-01' 会用到索引（覆盖索引）
注意这儿是 count(1) ，而不是 select *

INDEX WITH UNCLUDING COLUMNS (含列索引)

MySQL 通过拆表进行查寻优化的例子。

CREATE TABLE UserInfo(
userid INT NOT NULL AUTO_INCREMENT,
username VARCHAR(30),
registdate DATETIME,
email VARCHAR(50),
PRIMARY KEY(userid),
UNIQUE KEY idx_username(username,email),
KEY idex_ registdate(registdate)
);

SELECT email FROM UserInfo WHERE username=‘David' ;

这个查询可以在索引中取得数据，不需要回表，但复合索引的两个列都需要排序。
而含列索引的意思是索引中只对 username 进行排序，email 是不排序的，只是带到索引中，方便查找。

我们需要的其实是只对 username 进行排序，email 不需要排序，只要包含进来就行。

折成两张表：

CREATE TABLE UserInfo(
userid INT NOT NULL AUTO_INCREMENT,
username VARCHAR(30),
registdate DATETIME,
email VARCHAR(50),
PRIMARY KEY(userid),
UNIQUE KEY idx_username(username,email), <--- 这一行不要
KEY idex_ registdate(registdate)
);

CREATE TABLE idx_username_include_email(
userid INT NOT NULL AUTO_INCREMENT,
username VARCHAR(30),
email VARCHAR(50),
PRIMARY KEY(username,userid),
UNIQUE KEY(username)
);

对于含有多个索引的IOT表，可以将索引拆成不同的表，进而提高查询速度。但是实际使用中，就这个例子而言，使用复合索引，代价也不会太大。

MySQL中强制使用某个索引的语法

select * from employees force index(idxxxx) where ....

Multi-Range Read（MRR）

MySQL 的 IOT 表 employees，假如主键在 emp_no 列，hire_date 上面有一个非唯一索引，对于下的两个查询：

-- 查询语句1
mysql> select* from employees where emp_no between 10000 and 20000;
主键查找1W条数据，假设一个页中有100条记录，则只需要100次IO

-- 查询语句2
mysql> select * fromemployees wherehire_date >= '1990-01-01' limit 10000;
假设 聚集索引 和 hire_date索引 （二级索引）的高度都是 3 ，查找 1W 条记录：
第一次找到 hire_date>=1990-01-01 所在的页（二级索引）的IO次数为3
因为二级索引也是连续的，不需要从根再重新查找，第一次找到的页后，继续向后读页即可，这儿假设需要读 N 个页
3+N 就是在 hire_date （二级索引）中读取IO的次数
对于二级索引中找到的每一条记录，都需要回到 IOT 表去把所有数据取出来，对应 IO 次数据为3，1W条记录就是 3W 次 IO
所以，需要查询的总的IO数为 (3+N)+3W

在MySQL5.6之前，实际使用过程中，优化器可能会选择直接进行 扫表 ，而 不会 进行如此多的回表操作。

MRR：针对 物理访问 ，随机转顺序，空间换时间：开辟一块 内存 空间作为cache，将 需要回表 的 主键 放入上述的 内存 空间中（空间换时间）， 放满 后进行 排序 （随机转顺序）；，，将 排序 好数据（主键）一起进行回表操作，以提高性能；

◦ 在 IO Bound 的SQL场景下，使用MRR比不使用MRR系能 提高 将近 10倍 （磁盘性能越低越明显）；
◦ 如果数据都在内存中，MRR的帮助不大， 已经在内存 中了，不存在随机读的概念了（随机读主要针对物理访问）
◦ SSD 仍然需要开启该特性，多线程下的随机读确实很快，但是我们这里的操作是一条SQL语句，是 单线程 的，所以 顺序 的访问还是比 随机 访问要 更快

这片内存区域的大小由如下参数决定：
show variables like "read_rnd_buffer_size"; 默认32M，线程级，不建议设置太大，这个不在 buffer pool中，相当于 pga

MRR 功能默认就是打开的：
mysql> show variables like 'optimizer_switch'G
可以在命令的输出中看到 mrr=on

但是，MySQL 默认会做 MRR 成本计算，可能不会使用 MRR：
mysql> explain select * from employees where hire_date >= '1990-01-01';

在 5.6 和 5.7 中，基于 MRR 的成本计算是很悲观的，总是用不上，如果想强制使用 MRR，可以不让MySQL对MRR进行成本计算：
mysql> set optimizer_switch='mrr_cost_based=off';

求B+树的高度

每个页的 Page Header 中都包含一个 PAGE_LEVEL 的信息，表示该页所在B+树中的层数， 叶子节点 的PAGE_LEVEL为 0 。所以树的 高度 就是 root页 的 PAGE_LEVEL + 1
从一个页的 第64字节 开始读取，然后再读取 2个字节 ，就能得到 PAGE_LEVEL 的值

获取root页

mysql> select* from information_schema.INNODB_SYS_INDEXES where space<>0 limit 1\G
*************************** 1. row ***************************
       INDEX_ID: 18
           NAME: PRIMARY
       TABLE_ID: 16
           TYPE: 3
       N_FIELDS: 1
        PAGE_NO: 3    
          SPACE: 2
MERGE_THRESHOLD: 50
1 row in set (0.37 sec)

但这只能查询到 TABLE_ID,没有 TABLE_NAME，做一个关联查询即可：

use information_schema;
select b.name, a.name, index_id, type, a.space, a.PAGE_NO
from INNODB_SYS_INDEXES as a, INNODB_SYS_TABLES as b 
where a.table_id = b.table_id and a.space <> 0;

-- 聚集索引页的root页的PAGE_NO一般就是3

读取PAGE_LEVEL

mysql> select count(*) from dbt3.lineitem;
+----------+
| count(*) |
+----------+
| 6001215 |
+----------+
1 row in set(5.68sec)

shell> hexdump -h
hexdump: invalid option -- 'h'
hexdump: [-bcCdovx] [-e fmt] [-f fmt_file] [-n length] [-s skip] [file ...]
shell> hexdump -s 24640-n 2-Cv lineitem.ibd 
00006040 00 02
00006042

1、24640 = 8192 * 3 + 64

• 其中 8192 是我的页大小
• root页 的 PAGE_NO 为 3 ，表示是 第4个页 ，则需要 跳过 前面 3个页 ，才能 定位到root页 ，所以要 *3
• 然后加上 64 个字节的偏移量，即可定位到 PAGE_LEVEL

2、-n 2 表示读取的字节数，这里读取 2个字节 ，即可以读到 PAGE_LEVEL

• 根据上述 hexdump 的结果，root页中的 PAGE_LEVEL 为 2，表示该索引的高度为 3 （从0开始计算）