主键B+ Tree，二级索引B+ Tree及对应的查询过程分析

B+ Tree数据结构

mysql索引就是通过B+ Tree实现的

B+树的primary value（主要作用）是在block-oriented storage context 块存储环境下，in particular, filesystems，比如说文件系统中，来存储数据。

与B树对比，all records都被存储在树的leaf level，only keys are stored in interior nodes内部节点

B+树有一个非常高的fanout（扇出），typically on the order of 100 or more, which reduces the number of I/O operations required to find an element in the tree 减少I/O操作数量

扇出很高的好处是这个树不会很高

如果一个页 page里面有100条记录，有100个扇出，那么这个树会有多少条记录？

树的高度为1，那就是100个记录

树的高度为2，100个扇出就表示有100个页 100*100=10000个记录

树的高度为3，那就是100100100=100万个记录

从100万个记录，找一条记录，只需要找三个页就可以了

 

B+ tree height: 2

Records per page: 4

Fanout: 5

一共有5个扇出，就是有5个指针出来，来指向是向左查找还是向右查找。指针指向的是页page，也就是有5个page

non-leaf page：可以是25,50,75，也可以没有值，其只要起到指示去哪里找就可以了，搜索都是最后去leaf page获取的

leaf page：按顺序存储数据

问题：如果树的高度为3，那我想找到一条记录，只需要读3个页，那需要的时间是多少？

IOPS：IO Per second，对于机械硬盘，每秒100次IO是能做到的，体现磁盘的IO读写能力，一次I/O需要10ms

3/100 = 30ms（没走数据库cache的，应该是最慢的查询方式）

其根据主键进行查找，其实也是非常快的，30ms左右是正常的

这也是很多公司把慢查询设置为0.5=500ms秒的原因，0.5秒说明至少走了50个IO，这样就说明比较慢了。

但这样想实际上是存在问题的，如id>100,<200可能还需要扫描几个页，或order by的列没有设置索引

所以说0.5秒基本上说明所有执行的sql都是可以走索引的
 

主键B+ Tree

mysql innodb是索引组织表，索引即数据，数据即索引，索引组织表中数据也是索引的一部分。

主键索引

 

复合索引(Compound Index) B+ Tree

复合索引compound index(index with multi column)有什么好处呢？

 可以看到其不仅对a,b进行排序，对a列本身也是进行排序的，但对b列不排序

这也就是联合索引最左匹配原则的成因

 二级索引B+ Tree

 

 

在二级索引/辅助索引中，其叶子节点不存放数据本身，而是存放主键。二级索引secondary index的leaf page(叶子节点) store(存储) row indentifier (行标识符)，存储是key,PK值。

在二级索引中，也是做了排序的。

查询生命周期

从客户端，到服务器，然后在服务器上进行解析，生成执行计划，执行，并返回结果给客户端。其中“执行”可以认为是整个生命周期中最重要的阶段，这其中包括了大量为了检索数据到存储引擎的调用以及调用后的数据处理，包括排序、分组等。

结果集中的每一行都会以一个满足MySQL客户端／服务器通信协议的封包发送，再通过TCP协议进行传输，在TCP传输的过程中，可能对MySQL的封包进行缓存然后批量传输。

在数据库中进行读取页的操作，首先将从磁盘读到的页存放在缓冲池中，这个过程称为将页“FIX ”在缓冲池中。下一次再读相同的页时，首先判断该页是否在缓冲池中。若在缓冲池中，称该页在缓冲池中被命中，直接读取该页。否则，读取磁盘上的页。

 

 

每次读写数据都是通过Buffer Pool ；

当Buffer Pool 中没有用户所需要的数据时，才去硬盘中获取；

回表

对比一下不回表和回表在性能上的差异

不回表的情况

select * from employees where emp_no between 10000 and 20000;

 只要顺序的扫对应的页就可以了，看一下其IO成本

是10000条记录所在的页，假设每个页存放100条记录，那也就顺序扫描100个页

回表的情况

 hire_data是secondary index

select * from employees where hire_date >= '1990-01-01';

 假设聚集索引和二级索引B+树高度都是3，有10000条记录

• 3为第一次找到hire_date>=1990-01-01 所在的页（二级索引）的IO次数
• N为从第一次找到的页往后读页的IO次数（注意二级索引也是连续的， 不需要从根再重新查找）
• 所以3+N 就是在hire_date （二级索引）中读取IO的次数
• 30000为在索引组织表（主键B+ Tree）中进行回表的次数。每条记录都要回表，扫一个数据页，10000条结果要回表10000次，聚集索引3*10000=30000

可以看到有大量的回表，数据级是3+N+30000

 

在5.5之前，innodb都是这样做的。有的情况下，甚至innodb优化器都不回表了，可能我的聚集索引才10000个页，那其就直接遍历聚集索引来做了。

5.5之后，mysql提供了Multi-Range Read(MRR)

思路就是：随机转顺序，空间换时间

简单来说，就是其开辟了一块空间，本来是一条一条回表的，其会将一条一条回表的PK放到一个线程对应的cache里面，放满了做一个操作，根据主键排序，排序之后，再去回表，是不是就是比较顺序了。

这块内存，就是空间换时间，而排序，就是随机转顺序。

在索引设计方面，有两个思路：

1. 可以通过添加索引，从而使查询使用覆盖索引，无需回表即可查询到记录。代价是加入二级索引要维护其顺序。
2. 可以通过拆表来实现仅使用主键索引就满足查询功能。代价是拆开表后要进行两张表的同步。

回表优化案例

create table UserInfo(
    userid int not null auto_increment,
    username varchar(30),
    registdate datetime,
    email varchar(50),
    primary key(userid),
    key idex_registdate(registdate)
)

做下面的查询

select email from userinfo where username = 'david';

方法1：使用覆盖索引covering index(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)
)

这样可以，但是会带来一个副作用，我们并不需要对email进行排序，会影响插入顺序

 

方法2：拆表的使用场景1：index with included column

create table idx_username_include_email(
    userid int not null auto_increment,
    username varchar(30),
    email varchar(50),
    primary key(username, email),
    unique key idx_username(userid)
)


begin;
insert into UserInfo xxx
insert into idx_username_include_email xxx
commit;
-- better to use Stored Procedure

插入两张表没有问题，可以使用store procedure 一个事务或触发器trigger（本身就是事务的）来做

但是应用要改，应用要使用右侧这张表

select email from idx_username_include_email where username = 'david';

其实思路也是以空间换时间

通常可能并不会这样做，因为即便使用方法1复合索引，与这种拆表法相比，可能开销也不是很大