2018-07-12B+树

查询B+树索引的流程

首先通过B+树索引找到叶节点，再找到对应的数据页，然后将数据页加载到内存中，通过二分查找Page Directory中的槽，查找出一个粗略的目录，然后根据槽的指针指向链表中的行记录，之后在链表中依次查找。

需要注意的地方是，B+树索引不能找到具体的一条记录，而是只能找到对应的页。把页从磁盘装入到内存中，再通过Page Directory进行二分查找，同时此二分查找也可能找不到具体的行记录（有可能会找到），只是能找到一个接近的链表中的点，再从此点开始遍历链表进行查找。

四、聚簇索引与非聚簇索引

B+树索引可以分为聚集索引和辅助索引，他们不同点是，聚集索引的行数据和主键B+树存储在一起，辅助索引只存储辅助键和主键。

1.聚集索引

聚集索引是按每张表的主键构造的一颗B+树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的节点成为数据页，这个特性决定了索引组织表中数据也是索引的一部分。由于实际的数据页只能按照一颗B+树进行排序，所以每张表只能拥有一个聚集索引。查询优化器非常倾向于采用聚集索引，因为其直接存储行数据，所以主键的排序查询和范围查找速度非常快。

不是物理上的连续，而是逻辑上的，不过在刚开始时数据是顺序插入的所以是物理上的连续，随着数据增删，物理上不再连续。

2.辅助索引

辅助索引页级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别中的索引行中还包含了一个书签，该书签用来告诉InnoDB哪里可以找到与索引相对应的行数据。其中存的就是聚集索引的键。

辅助索引的存在并不影响数据在聚集索引的结构组织。InnoDB会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后通过主键索引找到一个完整的行记录。当然如果只是需要辅助索引的值和主键索引的值，那么只需要查找辅助索引就可以查询出索要的数据，就不用再去查主键索引了。

五、索引的管理

索引在创建或者删除时，MySQL会先创建一个新的临时表，然后把数据导入临时表，删除原表，再把临时表更名为原表名称。

但是在InnoDB Plugin版本开始，支持快速创建索引。其原理是先在InnoDB上加一个s锁，在创建过程中不需要建表，所以速度会很快。创建过程中由于加了s锁，所以只能进行读操作，不能写操作。

show index form table;是查看表中索引的信息的。

Table:索引所在的表名

Non_unique:非唯一的索引，可以看到primary key 是0，因为必须是唯一的

Key_name:索引名称

Seq_in_index:索引中该列的位置

Column_name:索引的列

Collation:列以什么方式存储在索引中。可以是A或者NULL，B+树索引总是A，即排序的。

Cardinality：表示索引中唯一值的数目的估计值。如果非常小，那么需要考虑是否还需要建立这个索引了。优化器也会根据这个值来判断是否使用这个索引。

Sub_part:是否是列的部分被索引。100表示只索引列的前100个字符。

Packed:关键字如果被压缩。

Null：是否索引的列含有NULL值。

Index_type:索引的类型。InnoDB只支持B+树索引，所以显示BTREE

六、Hash索引

InnoDB中自适应哈希索引使用的是散列表的数据结构，并且DBA无法干预。

https://blog.csdn.net/u012978884/article/details/52416997