MySQL(InnoDB剖析):InnoDB索引概述、数据结构与算法概述（二分查找、二叉搜索树、平衡二叉树、B+树）

• 索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响。要找到一个平衡点

• InnoDB支持以下几种常见的索引：
  
  
  
  • B+树索引
  
  
  • 全文索引
  
  
  • 哈希索引
  
  


• 前面已经提到过，InnoDB支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引


• B+树索引是传统意义上的索引，这是目前关系型数据库中查找最为常见和最有效的索引。B+树索引的构造类似于二叉树，根据键值快速找到数据

• 注意：B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入内存，再在内存中进行查找，最后得到查找的数据

• 二分查找法（binary search）也称为折半查找法，用来查找一组有序的记录数组中的某一记录，其基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半

  
  
  
  
  

演示案例

• 如有5、10、19、21、31、37、42、48、50、52这10个数，现在要从这10个树中查找48这条记录，其查找过程如下：

• 从上图可以看到，用来3此就查找到了。如果是顺序查找，则需要8次。如果要查找5这条记录，顺序查找只需1次，二分查找法需要4次


• 对于上面10个数来说，平均查找次数为（1+2+3+4+5+6+7+8+9+10）/10=5.5次。二分查找法为（4+3+2+4+3+1+4+3+2+3）/10=2.9次。在最坏的情况下，顺序查找的次数为10，而二分查找的次数为4

• 二分查找法的应用及其广泛。在前面也介绍过，每页PAGE Directory中的槽是按照主键的顺序存放的，对于每一条具体记录的查询是通过对Page Directory进行二分查找的

• 定义：
  
  
  
  • 二叉搜索树是一棵二叉树
  
  
  • 左子树的键值都小于父节点的键值
  
  
  • 右子树的键值都大于父节点的键值
  
  


• 例如下面就是一颗二叉搜索树

查找复杂度

• 查找5这个节点：
  
  
  
  • 那么先从跟查找，然后再查找左子树3，然后再查找右子树5，最终找到。一共找了3次
  
  
  • 如果通过中序遍历的话也需要3次
  
  


• 查找8这个节点：
  
  
  
  • 先找6，再找7，再找8，最终找到。一共找了3次
  
  
  • 如果通过中序遍历的话需要6次
  
  


• 总结：
  
  
  
  • 二叉树的平均查找次数为（3+3+3+2+2+1）/6=2.3次
  
  
  • 中序遍历的查找次数为（1+2+3+4+5+6）/6=3.3次
  
  
  • 因此，二叉搜索树的平均查找速度较快
  
  

• 平衡二叉树是根据二叉搜索树改进的一种树，例如我们有2、3、5、6、7、8这几个节点，通过下图所示的结构来建立二叉查找树，图中的平均查找次数为（1+2+3+4+5+5）/6=3.16次。因此查找效率比较低

• 平衡二叉树的定义：
  
  
  
  • 也是一颗二叉查找树
  
  
  • 但是左右子树的高度差最大为1，不能超过1，如果超过1，那么就不平衡了
  
  

单旋转

• 在上图所示的平衡二叉搜索树中插入节点9，那么就不是平衡的了，因为节点7的的左右子树高度差为2

• 因此需要做一次单旋转来回到平衡状态

双旋转

• 在上图所示的平衡二叉搜索树中插入节点3，那么就不是平衡的了，因为节点2的的左右子树高度差为2

• 因此需要做双旋转来回到平衡状态

• B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问方法（ISAM，这就是MyISAM引擎最初参考的数据结构）演化而来，但是在实现使用过程中几乎已经没有使用B数的情况了


• 下面我们对B+数进行精简的讲述：B+树是为磁盘或其他直接存储辅助设备设计的一种平衡查找树，由各叶子节点指针进行连接。先来看一个B+数，其高度为2，每页可存放4条记录，扇出（fan out）为5，图下图所示


• 从下图可以看出，所有记录都在叶子节点上，并且是顺序存放的，如果用户最坐左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排列：5、10、15、20、25、30、50、55、60、65、75、80、85、90

B+树的插入操作

• B+树的插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到B+树的三种情况，每种情况都可能会导致不同的插入算法。如下图所示：

Leaf Page未满、Index Page未满的插入

• 对于上面那张B+树所示，若用户插入28这个键值，因为Leag Page和Index Page都未满，因此可以直接插入，得到下图所示结果

Leaf Page已满、Index Page未满的插入

• 接着上图，我们再插入70这个键值，此时Leag Page已满但是Index Page未满，插入之后Leaf Page的情况为：50、55、60、65、70，此时中间节点为60，以60来拆分叶子节点


• 此时根据以下规则插入：
  
  
  
  • 查分Leaf Page
  
  
  • 将中间的节点（60）放入到Index Page中
  
  
  • 小于中间节点的记录（50、55）放左边
  
  
  • 大于或等于中间节点的记录（65、70）放右边
  
  


• 最终的结果过如下图所示（备注：下图没有在各叶子节点加上双向链表指针，不过与上图一样，它是存在的）：

Leaf Page已满、Index Page已满的插入

• 接着上图，我们插入键值95，此时Leag Page、Index Page都已满，因此需要做两次拆分，执行步骤如下：
  
  
  
  • 拆分Leaf Page
  
  
  • 小于中间节点的记录放左边
  
  
  • 大于或等于中间节点的记录放右边
  
  
  • 拆分Index Page
  
  
  • 小于中间节点的记录放左边
  
  
  • 大于中间节点的记录放右边
  
  
  • 中间节点放入上一层Index Page
  
  

旋转操作

• 从上面可以看到，不论B+树如何变化，最终都会平衡。因为B+树会不断进行拆分页操作。但是B+数主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作，所以B+树也提供了类似于平衡二叉树的旋转操作



• 原理：

  
  
  • 旋转发生在Leaf Page已满，但是其左右兄弟节点没有满的情况下
  
  
  • 这时B+树并不会急于去做拆分页的操作，而是将记录移动到所在页的兄弟节点上
  
  
  • 在通常情况下，左兄弟会被首先检查用来做旋转操作
  
  


• 再来看看上面“Leag Page未满、Index Page未满的插入”，如下图所示：

• 若插入键值70，其实B+树并不会急于拆分叶子节点，而是做旋转操作，得到下图所示的操作

B+树的删除操作

• B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值


• B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序


• 同插入一样，B+树的删除操作同样需要考虑下面的3种情况，与插入不同的是，删除根据填充因子的变化来衡量

表中删除的第一种情况（删除节点为叶子节点）：

• 例如根据上图，我们要删除70这条记录。因为70为叶子节点，因此直接删除这个叶子节点即可


• 最终的结果如下

表中删除的第一种情况（删除节点非叶子节点）：

• 接着上图，我们删除键值为25记录，但是该值还是Index Page中的值，因此删除之后要以其右兄弟节点（2）来代替。最终的结果如下

表中删除的第一种情况

• 接着上图，我们要删除60这个节点


• 删除Leaf Page中键值为60的记录后，File Factor小于50%，这时需要做合并操作，同样，再删除Index Page中相关记录后需要做Index Page的合并操作，最终的结果如下：