mysql那点事儿(一)

在实际应用中，索引是提供查询性能的重要途径之一。但也并不是意味着所建的索引越多越好，过多的索引会导致过高的磁盘使用率和过多的内存占用率。

索引尽量避免事后添加，此时添加索引的成本远高于设计之初。

那么作为在关系型数据库占据很大比重的mysql索引又是如何的呢？接下来将以mysql为例，讲述创建高性能索引的策略，以及其背后的工作原理【涉及数据结构和算法】

概论

常说索引一般都是B-Tree索引，它也是关系型数据库查询数据最为常见和有效的索引。不过在mysql中不同的存储引擎会使用不同的数据结构，比如innodb使用的是B+Tree(也称之为平衡树，与常说的二叉树是有差异的)，实际上B+Tree索引指向并不是具体的数据行，而是数据行所在的数据页。

页是计算机管理存储器的逻辑块，硬件及OS通常将主存和磁盘存储分割为连续大小相等的块，每个存储块即为页。

在存储系统中主存和磁盘都是以页来完成数据交换的。当程序需要的数据不存在主存，会向磁盘发出读盘信号，接下来就会将需要读取的数据所在的页甚至都读入到主存中，最后程序返回所有的数据。

一般在读盘过程中，并不是仅仅将需要的数据所在的数据页读入即可，而是将当前数据页甚至后续的好几页数据也一并读入，这就是数据预读取。减少读盘的损耗，以及充分利用主存的优势。

索引

• 数据结构
  在说明这个问题之前，我们先了解二叉树。首先要提到的就是二叉查找树，其原理其左边子树的值总是小于根的值，其右子树的值总是大于根的值。那么在正常情况下二叉查找优于顺序查找，不过这和我们在mysql中应用的B-Tree有着很大的差异。
  二叉树一般可以任意构造的，并不像平衡二叉树那么高效： 一般平衡二叉树是在二叉树的基础上构建的，并保证任意节点的两个子节点高度差不高于1.
• 数据读取
  在实际应用中查下性能越高也就意味着维护成本越大；这也是为什么mysql并不是直接使用平衡二叉树来作索引，随着数据量增加对应的索引数据也会增加。同时也意味着数据不能全部放到主存中，需要以索引文件的方式存储在磁盘上。由于磁盘读取和内存读取相差数个数量级，读取过程也会加大io消耗。
  若是将一个拥有上百万节点的二叉树都放到磁盘带来的io消耗是个非常恐怖的事情。所以减少io的次数是不得不面对的问题。
• 规避io损耗
  针对上面数据读取的问题，在mysql中采用的方法如下：
  比较有效的方法就是减少树的深度：将二叉树变n叉树，变成“多路搜索树”。
  1、数据都存放在叶子节点，非叶子节点不存放数据，并将所有的记录节点都按照键值大小排序的。
  2、所有的叶子节点都是指针链接
  这也是多路搜索树的重要两个特征，并且在mysql中叶子节点都是数据页的整数倍。在空间大小一定的情况下，每个节点能够存放足够多的内节点，这样保证节点索引范围大而准确。又由于叶子节点通过指针链接能够进行空间访问，也是基于这些mysql采用B+Tree作为索引存储结构，同时mysql也利用磁盘预读取的功能来减少磁盘io的消耗。

• B+Tree
  在mysql中写入数据时会出现分裂的问题，那么mysql又是如何解决的？
  在对应的插入数据时需要根据索引页查找到新数据所存放的叶子节点，此时需要检查下对应的索引页下的叶子节点是否有空缺，有的话直接插入，没有的话就需要进行分裂后再插入。
  比如插入28，首先在索引页找到28应该存放的位置[25,50],并且检查发现对应的叶子节点并没有满，则直接插入在索引节点25右边子树的[25,30]中

  
  叶子节点未满的实例.png
  

  再比如插入70
  首先查找索引页位于[50,75],再检查下面的叶子节点都已满，此时分裂就会闪亮登场。
  由于当前的数据应该位于索引节点50右边子树上，此时需要将该右边子树根据中间值进行拆分出叶子节点60 形成[50,60]、[60,70],通过分裂之后再重新查询对应的数据位于的索引页对应的叶子节点60，对应的数据刚好可以存放到其右边子树【并且右边子树未满】，此时数据插入完成

  
  叶子节点已满，分裂的应用.png
  若是当我们插入95呢
  发现此时的二叉树已满了，接下来的操作又该如何呢？
  此时就需要两次分裂：索引页分裂此时叶子节点是75，而需要插入的数据是95，需要将75的叶子节点右边子树按照中间值拆分85的叶子节点。形成[75,85]对应的数据范围(75,80,X,X) 和 (85,90，X，X)
  当整个二叉树都满了.png

经过两次分裂的最终二叉树.png

前面也提到B+Tree是平衡树，这样针对新插入的值都需要大量的拆分页的操作，进而带来的io消耗也是比较严重的。针对这个问题mysql使用类旋转的方式来规避

• 减少分裂io损耗的-旋转
  举个实际的例子：比如新插入数据时，若是当前叶子也已满，其兄弟节点并未满，此时并不直接来做分裂，而是将节点记录移到兄弟节点上，一般是按照先左后右的顺序。
  比如上述的插入70的操作
  将当前索引页的右边子树的最小的节点50移到左边子树的最末尾的空节点位置。这样右边节点就空出来位置填充70

  
  左旋转添加数据.png
  

  由此可见 通过旋转可以尽量减少页分裂的成本，减少维护索引带来的io成本。同时也提高索引的维护效率 。
  同理删除节点也是一样通过旋转和分裂来共同完成。

后记

更多内容可以借鉴<<高性能mysql>>