B+树索引

一、B+树

       mysql主要支持B+树索引、全文索引、哈希索引。

      B+树索引是最常见也是在数据库中使用最为频繁的一种索引，所以本文主要介绍B+树索引，但在此之前我们需要介绍一些与之密切相关的算法与数据结构，以帮助我们更好的理解B+树索引的工作方式。

      1、二分查找法

            二分查找法也被称为折半查找法，对于一组有序排列的数据，我们将数据中点位置的数据作为比较对象，若查找的对象小于该中点位置的元素，则将带查序列缩小为左半部分，否则为右半部分，通过一次比较便可将查找区间缩小一半。

     2、二叉查找树和平衡二叉树

             在介绍B+树之前，我们需要了解一下二叉查找树。B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。二叉树是一种经典数据结构，图1显示了一棵二叉树，二叉树中左子树的的键值总是小于根的键值，右子树的键值总是大于根的键值。因此可以通过中序遍历得到键值的排序输出。当然二叉树可以任意的构造，图2同样也是一棵二叉树，但图1中的查找到每个节点需要的次数为（3+3+3+2+2+1）/6=2.3次。但是图2中二叉树的平均查找次数为（1+2+3+4+5+5)/6=3.16次，所以此时查询效率就低了。所以若想要构建出性能最优的二叉树，则需要这棵二叉树是平衡的。

                   

                      图1                                                             图2

       

 

       3、平衡二叉树（AVL树）

          平衡二叉树定义：首先需要符合二叉查找树定义，其次必须满足任何节点的两个子树的高度最大差为1。

平衡二叉树的查找性能是比较高的，但不是最高的，只是接近最高性能。最好的性能需要建立一棵最优二叉树（霍夫曼树），但是最优二叉树的建立和维护需要大量的操作，所以我们只需建立一棵平衡二叉树即可。平衡二叉树的查询速度较快，但维护一棵平衡二叉树的代价较大，通长来说需要一次或多次左旋和右旋来得到插入或更新后的平衡性。

  

       4、B+树

           （1）B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问方法演变而来，在现实使用过程中几乎已经没有使用B树的情况了。B+树是为磁盘或其他直接存储辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。先看一个B+树，其高度为2，每页可存放4条记录，扇出为5，如图3。

                                                                     图3

 

       （2） B+树的插入操作

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

                                                               图4

        （3）B+树的删除操作

           B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小值，B+树的删除操作同样必须保证删除后的叶子节点中的记录依然排序，同插入一样，B+树的删除操作同一需要考虑三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

                                                          （图5）

 

二、b+树索引

        前面已经讨论了B+树的数据结构及其操作，B+树索引的本质就是B+树在数据库中的实现。但B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般在2-4层，所以我们查找某一键值的行记录时最多只需要2到4次 IO。B+树索引可以分为聚集索引（clustered index）和辅助索引（secondary index）有时也称非聚集索引，但是不管是聚集还是辅助索引，其内部都是B+树，即高度平衡，叶子节点存放着所有数据，聚集索引和辅助索引不同的点就是是，叶子节点存放的是否为一整行信息。

        2.1、聚集索引

        InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引(clustered index)就是按照每张表的主键构造一个B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个数据也都通过一个双向链表来进行链接。

       由于实际的数据页只能按照一个B+树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器更倾向与采用聚集索引，因为聚集索引能够在B+树索引的叶子节点上直接找到数据。

       2.2、辅助索引(非聚集索引)

       辅助索引的叶子节点并不包含行记录的全部数据。每个叶子节点中的索引行中还包含了一个书签。该书签用来告诉InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。辅助索引的存在并不影响数据在聚集索引中的组织，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获取指向主键索引来找到一个完整的行记录。

       2.3、B+树索引的分裂

       之前介绍的B+树的分裂是最为简单的一种情况，这和数据库中的B+树索引的情况略有不同，并且之前并没有涉及并发，而这才是B+树索引实现最为困难的部分。

        B+树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费。例如：1、2、3、4、5、6、7、8、9。插入是根据自增顺序进行的，若这时插入10，根据B+树插入操作，当叶子节点满时，小于中间记录放左边，大于等于的放在右边，以5为分裂点记录，得到下面两个页：

 P1:1、2、3、4         P2: 5、6、7、8、9、10

然而插入是顺序的，P1这个页中将不会再有记录被插入，从而导致空间的浪费。而P2又会再次进行分裂。

InnoDB存储引擎的Page Header中有一下几个部分用来保存插入的顺序信息:

       1、page_last_insert         2、page_direction    3、page_n_direction

       通过这些信息，InnoDB存储引擎可以决定是向左还是向右进行分裂，同时决定将分裂点记录是哪一个，若插入是随机的，则取页的中间记录作为分裂点的记录，这和之前介绍的相同。若往同一方向进行插入的记录数量为5，并且目前已经定位(cursor)到的记录(InnoDB存储引擎插入时，首先需要进行定位，定位到的记录为待插入记录的前一条记录)之后还有3条记录，则分裂点的记录为定位到的记录后的第三条记录，否则分裂点记录就是待插入的记录。

        如图6就是一个向右分裂的例子，并且定位到的记录之后还有3条记录，则split record为分裂点记录，最终

向右分裂得到如图7所示

                                                                            图6

 

                                                                          图7

      当分裂点就为插入记录本身，向右分裂后仅插入记录本身，这在自增插入时是普遍存在的一种情况。(图8)

                                                                            图8

 

 

三、B+树索引的使用

       3.1、唯一索引：create unique index 索引名称 on 表名(列名称)；

       3.2、简单索引：create index 索引名称 on 表名(列名称)；

       3.3、联合索引：

               联合索引是指对表上的多列进行索引，联合索引与单个索引创建的方法一样，不同之处仅在于有多个索引列。create index  索引名称  on 表名 (列1, 列2)；

               本质上说联合索引也是一棵B+树，但联合索引的键值数量大于等于2。假设两个键值的名称分别为a,b，如图9，从图中可以看出多个键值的B+树情况，和单个键值的B+树并没有什么不同，键值都是排序的，通过叶子节可以逻辑上顺序的读取所有数据，即(1,1)(1,2)(2,1)(2,4)(3,1)(3.2)。数据按（a,b）的顺序进行了存放。

                                                                       图9联合索引
        因此当我们查询select * from table where a=xxx and b=xx 时，显然可以使用该联合索引，对于单个的a列查询select * from  table where a=xxx也可以用该a,b索引，但是对于b列的查询select * from table where b=xxx,则不可以使用这棵树的索引，因为我们可以发现叶子节点上b的值为1、2、1、4、1、2显然不是排序的，因此对于b列查询使用不到a，b索引。这便是我们使用联合索引所要遵循的最左匹配原则。

         3.4、覆盖索引

         InnoDB存储引擎支持覆盖索引(covering index),即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，所以其大小要远小于聚集索引，因此可以减少大量的IO操作。

     例如当我们使用select count(*) from tableA where date>='2018-4-20' and date<='2018-4-22'  ，表tableAy有（userId,date)的联合索引，只根据列date进行条件查询，一般情况下是不能使用该联合索引的，但是这SQL查询是统计操作，并且利用到覆盖索引的信息，因此该优化器会选择该联合索引，