mysql索引优化原理（一）

        mysql索引无论是平日工作还是面试，都是避不开的。有时候记得住索引优化的注意要点，不如深入了解下mysql的索引原理，根据原理去理解优化点，方能事半功倍。

        首先索引是什么，索引是mysql高效获取数据的一种排好序的数据结构。而且是B+树结构。关于mysql索引的设计，因此需要从二叉树开始讲起，先贴图。

上面是最基本的二叉搜索树，想想，如果我们索引结构如上图，因为mysql是持久化数据库，那么mysql读取磁盘的耗费，花费在路上(即进行磁盘IO)的时间太长了，可以说不是很合理。哦，那就需要高度小点的咯。那么看看B树是个什么情况。

呦，B树确实符合要求，无论是数据查找还是磁盘IO消耗，确实都满足索引的要求。是的，mysql确实采用了B树的结构，但却有些变化，实际上B+树是B树的变种。那下面就看看具体的不同。

B树（上图）：

叶节点具有相同的深度；

叶节点的指针为空；

各节点中索引列值从左到右递增排列；

顺序访问指针，可以提高区间访问的性能；

B+树（上图）：

叶节点具有相同的深度；

B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，进行范围查找快；

各节点中的索引列值从左到右递增排列；

顺序访问指针，可以提高区间访问的性能；

非叶子节点不储存数行据data，只储存key值；

B+Tree索引的性能分析

一般使用磁盘I/O次数评价索引结构的优劣；

预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存；

局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用；

B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O；

B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)；

       首先，最大的不同点就是B树各节点上除了key值还存储了data，这就占据了比较大的空间。而mysql一般分配的容量（这里的容量指的是树每层相连一块，即一个度Degree所有节点加起来分配的空间，如图中15/56/77或者15/20/49或15/18）假如为16KB。而data元素占的空间比较大，导致每层的节点个数就比较少，树的高度比较高，磁盘进行IO消耗大。那么B+树父节点只存储了key值，只在叶子节点存储了data，显然高度小的多。而且高度一般为3到5之间。

       B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数 。我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16KB*1024/14=1170 个。一棵高度为2的B+树，如果一条数据大约为1KB的话，一个数据页为16KB，即能存放1170*16=18720 条这样的数据行。意味着高度为3的树叶子节点的整块节点也就为1170*1170 = 1368900个。OK，假设一个叶子节点存储的数据为16KB，最终能存储的数据大小为1368900*16KB = 21902400KB。换言之，对于mysql索引而言，至少能存储21902400条数据。千万级别的数据查询，通过索引就能够快速查询，这并不是没有道理的。

PS:hash表结构速度真的特别快，不考虑hash碰撞，有一主要缺点就是无法很好的进行范围查询。而B+树叶子节点增加了双向指针，进行范围查找快。