MYSQL数据库索引B+树结构_Mysql

1影响数据库数据查询效率的因素

mysql数据库innodb存储引擎使用b+树作为索引存储数据结构。数据库数据查询效率主要受io次数影响，一次磁盘io为硬盘的机械运动，包含：

寻道时间：指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；
旋转延迟：就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；
传输时间：指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计

所以一次磁盘io会消耗10ms左右的时间，如果数据库查询过程中磁盘io次数过多，会极大的影响查询效率。

2b+树介绍

2.1b+树的数据是如何存储到磁盘上的

本文以高度为3的b+树为例，包含根节点、内部节点（根节点及叶子节点以外的节点）和叶子节点：

其树结构中的每一个节点，对对应innodb存储引擎的一个逻辑页，一个逻辑页是默认大小为16kb的连续物理磁盘空间，逻辑页可配置；根据b+树的特性，其根节点和内部节点对应的逻辑页仅用于存储索引键值以及指向其子节点的指针，叶子节点用于存储实际数据行；

每个节点内部的数据即节点对应的连续物理磁盘空间上的数据都是按顺序排列的，且每个叶子节点还包含一个指向下一个叶子节点的指针，使各个叶子节点的元素可以视为一个顺序链表：

2.2基于b+树的数据查询过程

首先innodb存储引擎会将b+数的根节点数据预先加到到内存中，从根节点开始，使用二分查找获取目标值，找到目标值后若当前页非叶子节点，则会根据指针对应地址在将对应页的数据从磁盘读入内存，再次通过二分查找定位目标值，重复上述操作，直到定位到叶子节点对应的页数据，最后从叶子节点中获取到目标数据。

其中读取一页数据对应着一次磁盘io，即一次查询中，树的深度对应着磁盘io次数。

3.为什么使用b+树数据结构

3.1为什么不使用（平衡）二叉树

由上一个章节可知影响查询效率的一个重要因素是树的深度，在二叉树的数据结构中，包括平衡二叉树（avl树、红黑树）是每个节点只存储一个键值和数据的。即每个磁盘块仅仅存储一个键值和数据！如果我们要存储海量的数据，可以想象到二叉树的节点将会非常多，高度也会及其高，我们查找数据时也会进行很多次磁盘io，我们查找数据的效率将会极低！

3.2b树

b树针对这个问题进行了优化，b树属于多叉树又名平衡多路查找树，参考2.1，与b+树类似，其每个节点对应innodb存储引擎的一个逻辑页，每个节点存储索引值和具体的数据：

其相较于平衡二叉树，存储相同数据量的情况下，树深度大幅降低，极大提升了查询效率；但b树在非叶子节点中也存储了具体数据行，数据行相较于索引值和指针的键值对会占用更大的存储空间，即b树结构下一个节点中存储的键值对数量会受具体数据行大小影响；

3.3b+树

b+树针对这个问题做了进一步优化，b+树则只在叶子节点中存储具体的数据行，非叶子节点则仅存储索引值和指向子节点地址的指针，尽可能让一个节点存放更多的键值对，即相同深度的b树和b+树，b+数存储的数据量相较于b树会更大。并且b+树子节点数据可以形成一个顺序链表，对范围查询等有更好的支持。

3.4b+数存储的数据量估算

参考2.1，b+树每个节点对应innodb存储引擎的一个逻辑页，假如索引键值为8字节，innodb设置的指针大小为6字节，即一个键值对占14字节，一个逻辑页16kb，则一个节点内可以存储【16*1024/14≈1170】个键值对，粗略假设每个数据行占1kb，则一个叶子节点对应的页可以存储16条数据，则一颗深度为m的b+树可以存储的数据条数为：非叶子节点指针个数 ** (m - 1) * 单个叶子节点数据行数【1170 ** (m - 1) * 16】,即深度为3的b+树可以存储的数据量为：

1170 * 1170 * 16 ≈ 21902400