MySql------B+树索引----InnoDB

前提

各个数据页可以组成一个双向链表
每一个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表
每个数据页都会存储一个页目录，在通过主键查找时，可以通过二分查找定位到相应的槽，然后顺序遍历槽对应的分组中的记录

没有索引的查找

精确查找：select * from 表名 where 列名=xxx

在一个数据页中查找

通过主键查找

通过页目录二分
然后在对应的分组中进行顺序查找

通过其它列查找

只能顺序查找

在很多数据页中查找

从第一个页开始顺序查找
在页中顺序查找

索引

create table index_demo(
    c1 int,
    c2 int,
    c3 char(1),
    primary key (c1)
) row_format= compact;

通过compact行格式存储各个信息

记录头信息格式

以下简化Compact格式：

record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1我们还没用过，等会再说
next_record：记录头信息的一项属性，表示下一条相对于本条记录的地址偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁
各个列的值：这里只记录在index_demo表中的三个列，分别是c1、c2和c3
其它信息：包括隐藏列，如果没有定义主键，送一个row_id作为主键；一个事务id、一个roll_pointer

insert into index_demo values(1,4,'u'), (3, 9 'd'), (5,3,'y');

insert into index_demo values(4,4,'a');

简单的整理一下

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

继续插入

整理下：将每页中的最小记录，提取出来，建立一个目录项

举个栗子

假如我们要找主键值为20的记录

先从目录项中根据二分法快速确定主键值为20的记录在目录项3中（12 < 20 < 209）
再根据前边说的在页中查找记录

这个目录项有一个别名，索引

InnoDB中的索引方案

复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录

record_type:

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

编号为30的页专门来存储目录项记录

通过主键查找：

先从目录项页中二分
再到数据页中二分

当目录项记录过多时：再添加一层

B+树结构

叶子节点：数据页

内节点：目录项

根节点：最大的目录项

索引

聚簇索引

InnoDB为我们自动的创建以主键建立的索引：称为聚簇索引，找的时候，直接找就完事了，找到叶子节点就是我们想要的数据

二级索引

我们以自己的想法建立索引，假如以C2建立索引

页内的记录是按照c2列的大小顺序排成一个单向链表
各个存放用户记录的页也是根据页中记录的c2列大小排成一个双向链表
存放在目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表

查找：

先找到叶子节点，然后找到对应的主键值，最后再回到聚簇索引中找最终值。

但是这样会有问题

内节点中目录项记录的唯一性

当我们要插入（9,1,'c'）时，出问题；不知道插到哪个页中去

所以：二级索引应包含

索引列的值
主键值
页号

InnoDB：索引即数据

MyISAM索引简单介绍

将表中的记录按照记录的插入顺序单独存储在一个文件中，称为数据文件

　　2. 索引信息另外存储在一个称为索引文件的文件中，只不过索引的叶子节点中存储的不是完整的用户记录，而是主键值+行号

　 3. 通过索引找到相应的行号，再去找对应的记录

创建和删除索引的语句

create table 表名(
    列信息，
    key或者index 索引名 （需要被索引的列1，列2...）
）

alter table 表名 add key或者index 索引名 (需要被索引的列1，列2);

alter table 表名 drop index或者key 索引名；


#假如想要索引c2和c3列，那么我们的索引名为：idx_c2_c3