Mysql中B+Tree索引结构、遍历次数、磁盘io次数分析

Mysql中B+Tree索引结构、遍历次数、磁盘io次数分析
一.Mysql数据库常见存储引擎

1.可以作为索引文件的数据结构：
二叉树，红黑树，hash表，B-tree，B+tree，但是二叉树，红黑树受到树高问题限制，hash表无法进行索引排序无法进行查询，B-tree无法充分利用非叶子节点的存储能力，所以在mysql数据库中最常用的索引存储数据结果为B+tree；

2.索引文件组织结构：
聚簇索引：索引字段+全部其他表字段保存在一个文件中，索引树的叶子节点即表中全量数据；
非聚簇索引：索引字段和表中全量字段分两个文件进行保存，索引树的叶子节点中存储对应全量数值在磁盘上的地址；

3.mysql数据库中常用的存储引擎：
MyISAM：采用非聚簇索引，不支持行级锁，不支持事 务；数据结构如下图所示：

innoDB：采用聚簇索引，支持行级锁，支持事务，MVCC机制等；数据结构如下图所示：
主键索引聚簇
辅助索引非聚簇（但在叶子节点中会保存主键索引树中的对应的值，便于回表使用）

二.B+tree索引文件结构及索引树遍历情况
1.索引文件组织结构
非叶子节点不存储data，只存储索引(冗余)，可以放更多b的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能
如下图所示：

在B+tree索引的表空间Tablespace 中具有以下几个概念：

• 段：一个索引2段：叶子节点Segment & 非叶子节点Segment；
• Extent（1MB）：一个Extent(1M) 包含64个 Page(16k),一个Page里包含很多有序行数据 , InnoDB B-Tree 一个逻辑节点就分配一个物理Page；
• Page(16KB)：B+tree中每个数据节点就是一个page
• Row：记录行
• Field：字段

2.MYISAM和innoDB索引树遍历过程
MYISAM存储引擎
MYISAM存储引擎中主键索引和辅助索引都都采用非聚簇形式，在磁盘中一共有三个文件进行数据存储分别为，数据数据定义文件，索引文件，数据文件；
执行数据查询时索引树的遍历流程为：
a.将磁盘索引文件的根节点的page加载到内存，进行二分查找定位到子节点的page，依次递归加载相应的page，找叶子节点data中磁盘地址；
b.根据data中的磁盘地址去数据文件中加载相应的数据到内存；

innoDB存储引擎
innoDB存储引擎的主键索引采用聚簇索引，辅助索引采用非聚簇；拥有一个数据定义文件和一个索引文件（索引+其+其它字段合并）
执行数据查询时索引树的遍历流程为：
主键索引： 确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过 二分查找找到记录或未命中。
辅助索引：通过二级索引查出对应主键，拿主键回表查主键索引得到数据， 二级索引可筛选掉大量无效记录，提高效率（ 回表就是通过辅助索引拿到主键id之后，要再去遍历聚集索引的B+树，这个过程就叫做回表。回表的操作更多的是随机io,随机io在性能上还是比较低）

全表扫描：直接读取叶节点头结点， 顺序扫描， 返回符合条件记录， 到最终节点结束

三.聚集索引和非聚集索引执行一次sql的io次数
磁盘io次数分析
（1） 数据量小的话，直接把索引放到内存中，内存的O(logn)消耗是远远低于磁盘io的,所以可以忽略不计
（2） 数据量大的话，采用索引结构，我们这部分先从二叉树说起，对于普通二叉树，第一个步骤是二分，每次判断都是一次半数的数量级检索。假如有100W的数据，大概的时间复杂度是：log2N=1000000即N=20的节点获取，也就是磁盘I/O复杂度最大为O(20)，二分的时间复杂度是O(log2N)。
（3） 但是对于数据库来说，存储场景会更加复杂，二叉树的性能虽然好，但我们还是想要树的高度更低一些，存储的数据更多一些。因此mysql引入了B+树的概念。除了根节点之外，第二层级的数量得到了充分的扩展，相对于普通的二叉树，B+树的结构更加庞大又不失美感，假设非叶节点不同元素占用情况为：下一条记录指针占4Byte，id值8Byte，目标记录指针4Byte，那么一个4Kb的磁盘块将大致可以容纳250个下级指针，100万行目标记录(假设叶子节点也是只保存了id值，则一个非叶子节点下面也包括大概250个叶子节点)只需log250N=1000000即N=3的I/O次数，充分提升了每次节点I/O带来的检索效用，时间复杂度是O（lognN）,这里的n是非叶子结点的个数。（PS：实际上innodb的数据页大小是16kb，这个n会更大，那么对应的，io次数也会更少）
（4） 在实际的查询中，IO次数可能会更小，因为有可能会把部分用到的索引读取到内存中，相对于磁盘IO来说，内存的io消耗可以忽略不计。一般来说B+Tree的高度一般都在2-4层，MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作（根节点的那次不算磁盘I/O）。

多大的索引数据可以直接放到内存中
要参照自己的mysql设置，一般是innodb_buffer_pool_size的值，这个值默认是128M，具体的要根据机器的性能设置。