MySQL调优(三)MySQL底层数据结构和索引系统

上一篇文章（MySQL底层架构及日志类型）我们了解了MySQL的底层架构图和日志类型以及数据的更新流程;
本文我们将进一步了解MySQL的数据结构和索引系统。

一、MySQL的数据结构

为什么MySQL的索引格式不用hash表、二叉树或者红黑树而是B树？
hash表的索引格式：

• 利用hash存储的话需要将所有的数据文件添加到内存，比较耗费内存空间；
• 如果所有的查询都是等值查询，那么hash确实很快，但是企业或者实际工作环境中范围查找的数据更多，而hash不太适合范围查询。

二叉树和红黑树的索引格式：
由下图可见，无论是二叉树还是红黑树，都会因为数的深度过深而造成io此时变多，影响数据的读取效率。

B树的索引格式：

• 所有键值分布在整棵树中；
• 搜索有可能在非叶子节点结束，在关键字全集内做一次查找，性能逼近二分查找；
• 每个节点最多拥有m个子树；
• 根节点至少有2个子树；
• 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）；
• 所有叶子节点都在同一层，每个节点最多可以m-1个key,并且以升序排列。
  

示例图说明：

• 每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针；
• 指针存储的是字节的所以磁盘块的地址；
• 两个关键词划分成的三个范围域对应三个指针指向的字数的数据的范围域；
• 以根节点为例：关键子为16和34，p1指针指向的子树的数据范围为小于16，p2指向的子树的数据范围为16-34，p3指向的子树的数据范围大于34。

查找关键字的过程：
1、根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2、比较关键字28在区间16-34，找到磁盘块1的指针p2。
3、根据p2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4、比较关键字28在区间25-31，找到磁盘块3的指针p2。
5、根据磁盘块3的p2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6、在磁盘块8中的关键字列表中找到关键字28。
由此可见也有其缺点：
1、每个节点都有key,同时也包含data,而每个也存储空间是有限的，如果data比较大的话会导致每个节点存储的key数量变小；
2、当存储的数据量很大时会导致深度较大，增加查询时磁盘IO次数，而影响查询性能。
所以需要进一步优化其数据结构，进化成B+Tree。

二、MySQL索引系统

从下图我们可以看出B+Tree是在BTree的基础之上做的一种优化，变化如下：
1、B+Tree每个节点可以包含更多的节点，原因1：为了降低树的高度；原因2：将数据范围变为多个区间，区间越多，数据检索越快。
2、非叶子节点存储key,叶子节点存储key和数据；
3、叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查找性能更高。因此可以对B+Tree 进行两种查找运算：
1）对于主键的范围查找和分页查找；
2）从根节点开始，进行随机查找。

下面我们延伸了解下MySQL InnoDB 的B+Tree 和MyISAM的B+Tree：