B-树与mysql索引

4170阅读　0评论2013-10-11　joepayne
分类：Mysql/postgreSQL

    本文主要分为两部分：B-树的数据结构，以及mysql索引
    B-树类似红黑树，都属于平衡多路查找树，但是每个节点的孩子节点不限于左右孩子，有的甚至上千，是因此储存同样一批关键字集合B-tree的高度更低，假设一个节点占满磁盘的一个页块，那么读取height(B-tree)次磁盘就能定位到该集合的任何关键字了，这是红黑树所做不到的，然而红黑树却表示不屑，因为一旦进入主存，红黑树是不二的搜索树（java里面的TreeMap就是用的红黑树），只能说各有各适合的业务场景


磁盘结构



其中灰色的一圈一圈的叫磁道，多个盘片的同一号磁道在立体上构成一个柱面，我们说的页块就分布在上面，大小从2k到16k不等，要读取一个节点，以7200RPM转速的硬盘为例，转一圈需要8ms，考虑到磁头的移动，常规磁盘的平均存取时间大约在10ms左右，跟内存的ns差了好几个数量级，因此系统要读的话一次会预读相邻的多个页块并缓存到内存里，如果你选择的是InnoDB这样的存储引擎，select的范围查询（特指跨多个页块）跟等值查询都只用读取一次磁盘

B树定义

    假设每个节点有1000个关键字，B-tree高度为2时，整棵树的容纳的关键字数目是1000+1000×1000，当高度为3时为1000+1000×1000+1000×1000×1000=十亿，海量有木有！看起来很爽，然而上面也提到了，这里所说的关键字实质是一条数据库记录，一个16k的页块其实容不下1000条记录

    让我们先从算法的角度来考虑这个问题，对于叶子节点，因为自身不做索引，大点没关系，但是非叶子节点则不然，如果一条记录过大了会影响孩子节点的个数，我们可以把非叶子节点的除关键字之外的数据——卫星数据，移动到叶子节点上面去，从而使得非叶子节点容量最大化，这就是B树的变种B+树

如图所示，d3本来是关键字3的卫星数据，现在被移动到叶子节点来了，这样索引节点就只用保存一个int类型的关键字和一个指向孩子节点的指针，一页块索引1000个孩子节点的愿望完全有可能,为了简单起见下面的伪代码我们用关键字代表整条记录

B树操作


1.查找

定义x.k(i)为x的第i个关键字，x.c(j)为x的第j个孩子节点


点击(此处)折叠或打开

  1. search(x,key)
  2.     i=1;
  3.     while i<x.n and key>x.k(i)//找到最小的下标，满足key<=x.k(i)
  4.     i++;
  5.     if key==x.k(i)//找到关键字了
  6.         return(x,i);
  7.     elseif x.leaf//已经到叶节点了，查找失败
  8.         return NIL;
  9.     else
  10.         READ_FROM_DISK(x.c(i));//从磁盘读取x的第i个孩子节点到内存
  11.         return search(x.c(i),key);//在孩子节点内递归查找关键字key


B-树的查找是从根节点开始的，因此入参为待查找的节点和要查询的关键字key，上面的伪代码清晰的演示了B树上查找与读取磁盘的关系：树有多高，最多读取多少次

下面提一下可能遇到的问题

  1. 在某个节点内部查找关键字key时，用哪种算法性能最好(有经验的同学可能都知道，二分法查找是mysql默认的页块内部查找算法，但这其中又有什么原理)

  2. 理论上讲，查找的返回应该为key所在的节点x和使得x.k(i)=key的下标i，但是实际情况是，一张表除了主键索引外可能还有关键字可以不唯一的二级索引，因此等值查询的返回可能不止一条记录，这又如何处理

  3. 上面说的问题都只是对于B-树的，如果换成了B+树，情况会怎么样？

对于第一个问题，我们知道含有N个关键字的B树的高度是logtN，在节点内线性查找一个关键字的时间复杂度为O(t)，而使用二分法则是log2t，此时查找整棵B树的时间复杂度为logtN*log2t=log2N，这样就使得查找时间复杂度跟红黑树一致了

对于第二个问题，我们首先确定查找到底返回什么，不考虑结果集跨页块，返回应该是关键字所在的节点以及该关键字在节点内的上边界下标以及下边界下标，因此在二分法定位到等值的关键字后，我们还得定位到上下边界：如果通过遍历来确认，一旦碰到整个节点的关键字都一样或大部分一样这样的bad case，这与我们的初衷又背离了;其实我们可以继续使用二分法，只要稍微改进一下即可，下面演示如何确定下边界


点击(此处)折叠或打开

  1. if (x.rec[mid - 1].key == key) {//已经确定到关键字key的下标mid了，找下边界 downMid
  2.     int upi = i;//i为二分法停止时的下边界，i<=key
  3.     int upj = mid;
  4.     while (upi < upj) {
  5.         downMid = upi + (upj - upi) / 2;//防止溢出
  6.     if (x.rec[downMid].key == key) {
  7.         upj = downMid;
  8.     } else {
  9.         upi = downMid;
  10.     }
  11. }


完整代码见

对于第三个问题，使用B+树的话上面的情况只会更好，看过search(Node x, int key) 方法后，意识好一点的同学应该能发现如果关键字跨节点的话（这也告诉我们建索引的字段重复率不易太大），B-树查找会退化成中序遍历多路平衡树，这是我们不愿意看到的，但是B+树有个好处，我们存的全部数据都在高度一样的叶子节点上，我们完全可以对叶子节点建立一个链表，使得中序遍历变成了顺序遍历，各项复杂度大大降低，如果你选择的是InnoDB这样的聚簇索引，卫星数据d也是按照关键字的顺序紧密排布在叶子节点上的，这样范围查询读取记录的效率就比较高

2.创建一颗空树


点击(此处)折叠或打开

  1. create(T){
  2.     x=new Node()
  3.     T.root=x
  4. }


3.插入

B-树只能在叶子节点上插入，碰到满节点就向上分裂，如果满的节点是根节点，树高度+1;

如果一个节点的关键字的数量到了2t-1,就得先对其进行分裂操作了（对于mysql只要剩余页面低于1/16就会触发分裂）：


点击(此处)折叠或打开

  1. split-child(x,i){//分裂x节点的第i个孩子节点y
  2.     y=x.c(i)
  3.     z=new Node(); //创建新的节点（这里是重点），用来存放满节点的后半段
  4.     y.n=z.n=t-1;
  5.     for j=1 to j=t-1//将满节点y的后半段备份到z上面去
  6.         z.k(j)=y.k(t+j);
  7.         z.c(j)=y.c(t+j)
  8.     z.c(t)=y.c(2t)
  9.     for j=x.n to j=i+1 //将x节点的i的后面半段平移一个单位
  10.         x.k(j+1)=x.k(j);
  11.         x.c(j+2)=x.c(j+1);
  12.     x.k(i+1)=x.k(i);
  13.     x.k(i)=y.k(t); //y最中央的关键字提升到x节点上面来
  14.     x.c(i+1)=z;


接下来插入就很简单了


点击(此处)折叠或打开

  1. insert(T,k){//在B树T上插入关键字k
  2.     r=T.root;
  3.     if(r.n==2t-1)    //如果根节点已满，先替换再分裂
  4.         s=new Node();
  5.         T.root=s;
  6.         s.leaf=false;
  7.         s.n=0;
  8.         s.c(1)=r;
  9.         split-child(s,1);
  10.         insert-nonfull(s,k);
  11.     else insert-nonfull(r,k);
  12. }



点击(此处)折叠或打开

  1. insert-nonfull(x,k){//在非满节点x上插入关键字k
  2.     i=x.n;
  3.     if(x.leaf)
  4.         while i>=1 and k<x.k(i)//如果是叶节点，边平移边找插入点
  5.             x.k(i+1)=x.k(i);
  6.             i--;
  7.         x.n++
  8.         x.k(i+1)=k;
  9.     else
  10.         while i>=1 and k<x.k(i)//如果是非叶节点，找待插入的孩子节点
  11.             i--;
  12.         i++;
  13.         if(x.c(i).n==2t-1)//如果待插入的孩子节点是满的，先分裂
  14.             split-child(x,i);
  15.             if(k>x.k(i))
  16.                 i++;
  17.         insert-nonfull(x.c(i),k)


看完插入后我们可以提出几个问题

  1. 插入的时间复杂度是多少

  2. 插入的性能开销怎么算

  3. 紧跟查找中提到的聚簇索引与非聚簇索引，这对于我们插入的有什么影响

对于第一个问题，我们可以继续使用二分法在节点中快速定位到待插入的位置，因此插入时间复杂度依然是 log2N

对于第二个问题，就不像查找时那样有个稳定的结果了，主要体现在分裂时创建新节点以及那两个for循环上，分配一个新的页块需要调用OS底层函数，那两个循环需要来回复制数据，并且最终修改并写入了三个磁盘页块

对于第三个问题，可以理解为数组VS链表在外存中的延续；对于随机插入，聚簇索引会十分不利，因为插入一个关键字key后，key后面所有的记录都要被向后平移一个单位，如果是二级索引还好，要平移的数据只是主键索引字段，量小，如果在主键索引上玩这个，就相当于对整张表所有记录做平移，后果非常严重，删除也是一样，key后面的记录需要向前靠拢；而非聚簇索引则没有这么多麻烦，所有叶子节点像链表一样，关键字到实际的每条记录用指针连接起来，插入只需要修改一下指针即可

mysql索引


上面的都是理论基础，接下来对比一下我们生产中遇到的mysql两种索引方式

这是非聚簇索引的示意图


某表有多个字段，其中对姓名name建立主键索引，其余字段用...代替，我们可以看到实际存放记录的堆跟B+树的叶节点是隔离的，其中叶节点只有两个字段：name以及指向真实记录的指针

由此我们可以得到三个结论：

  1. 非聚簇索引的索引文件跟数据文件是分开存放的，这有一个好处，在主键上求count(id)之类的操作会非常的快，因为只需要读取索引文件即可

  2. 插入和删除操作开销会非常的小，因为叶节点不强制顺序排列，更重要的是更笨重的实际记录没有保存在B+树上，插入删除只需修改叶节点上的指针即可

  3. 如果我们进行的范围查询，比如说查询姓名从以M开头的到以P开头的记录，如图所示，我们得读取4个物理并不连续的页块，甚至很有可能不在同一个柱面上，因此开销较大

这是聚簇索引的示意图

还是一样的表，字段name上建立主键索引，跟非聚簇索引相比，它有如下特点：

  1. 全部记录都存放在叶子节点上且物理上连续排列，因此索引相同数量的记录，聚簇索引的叶子节点数量较非聚簇索引会多上好几倍（与每条记录的长度成正比，因此不按范式拆表这里就会有问题），对应的非叶节点（即索引节点）也会多上好几倍，如果你的count(*)这类扫索引的操作很频繁的话，聚簇索引可能不是你的菜

  2. 插入和删除操作讲理论时就已经提到过了，如上图所示，插入一个Ota后面的所有记录都需要平移，性能很差

  3. 范围查询聚簇索引正好可以发挥威力

  4. 最后一点，行级锁;算法导论上B树的操作漏掉了sql里很重要的一项功能：update，我们只需要在叶子节点上维护一个长度为当前节点下记录数量的bitmap，很容易就能将update的锁粒度降至一条记录，这对于提高系统并发量很有帮助，这么做的保障除了update不会修改B树结构外，我想很大一部分原因是来自于数组这种简单的存储方式，才使得InnoDB的设计者敢出奇招

总结

虽然本文有点长，而且涉及到较多的对比，但是大家只需要在脑海中明确两个概念即可记住全部：

  1. B树是多孩子版的平衡搜索树，目的是为了迎合计算机科学的局部性原理：更小的树高+利用磁盘预读，而B+树是叶子节点囊括了非叶子节点关键字的B树

  2. 外存中的聚簇索引跟非聚簇索引就好比内存中的数组跟链表，一个更适合遍历（当然是指全部记录），一个更适合插入删除

B树的算法部分以及mysql两种索引方式就讲完了，还望大家在实际生产的过程中具体问题具体分析，权衡各项指标以确定使用mysql的方式，这样才能使得数据库不至于沦为你的系统的瓶颈

上一篇：快排的一种优化算法
下一篇：构造函数与析构函数