不懂数据库索引的底层原理？那是因为你心里没点b树

本文在个人技术博客不同步发布，详情可用力戳
亦可扫描屏幕右侧二维码关注个人公众号，公众号内有个人联系方式，等你来撩...

  前几天下班回到家后正在处理一个白天没解决的bug，厕所突然传来对象的声音：
  对象：xx，你有《时间简史》吗？
  我：我去！妹子，你这啥癖好啊，我有时间也不会去捡屎啊！
  对象：...人家说的是霍金的科普著作《时间简史》，是一本书啦！
  我：哦，那我没有...
  对象：人家想看诶，你明天帮我去图书馆借一本吧...
  我：我明天还要改...
  对象：你是不是不爱我了，分手！
  我：我一大早就去~
  第二天一大早我就到了图书馆，刚进门就看到一个索引牌，标识着不同楼层的功能，这样我很快能定位到我要找的目标所在的楼层了。
  

  我到楼上后又看到每排的书架上又对书的分类进行了细分，这样我能更快的定位到我要找的书具体在哪个书架！
  并且每个楼层都有一台查询终端，输入书名就能查到对应的唯一标识“索书号”，类似于P159-49/164这样的一个编码，书架上的书都是按照这个编码进行排序的！有了这个编码再去对应的书架上，很快就能找到对应的书在书架的具体位置了。
  

  不到十分钟，我就从图书馆借好书出来了。
  这么大的图书馆，我为什么能在这么短的时间内找到我要的书？如果这些书是杂乱无章的堆放，或者没有任何标识的放在书架，我还能这么快的找到吗？
  这不禁让我想到了我们开发中用到的数据库，图书馆的书就类似我们数据表中的数据，楼层索引牌、书架分类标识、索书号就类似我们查找数据的索引。
  那我们常用的数据库的索引底层的一个数据结构是什么样的呢？想到这里我又回到图书馆借了一本《数据库从入门到放弃》！
  要了解数据库索引的底层原理，我们就得先了解一种叫树的数据结构，而树中很经典的一种数据结构就是二叉树！所以下面我们就从二叉树到平衡二叉树，再到B-树，最后到B+树来一步一步了解数据库索引底层的原理！
二叉查找树（Binary Search Trees）

  二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树有如下特性：

1、每个结点都包含一个元素以及n个子树，这里0≤n≤2。
2、左子树和右子树是有顺序的，次序不能任意颠倒。左子树的值要小于父结点，右子树的值要大于父结点。

  光看概念有点枯燥，假设我们现在有这样一组数[35 27 48 12 29 38 55]，顺序的插入到一个数的结构中，步骤如下

  好了，这就是一棵二叉树啦！我们能看到，经通过一系列的插入操作之后，原本无序的一组数已经变成一个有序的结构了，并且这个树满足了上面提到的两个二叉树的特性！
  但是如果同样是上面那一组数，我们自己升序排列后再插入，也就是说按照[12 27 29 35 38 48 55]的顺序插入，会怎么样呢？

  由于是升序插入，新插入的数据总是比已存在的结点数据都要大，所以每次都会往结点的右边插入，最终导致这棵树严重偏科！！！上图就是最坏的情况，也就是一棵树退化为一个线性链表了，这样查找效率自然就低了，完全没有发挥树的优势了呢！
为了较大发挥二叉树的查找效率，让二叉树不再偏科，保持各科平衡，所以有了平衡二叉树！
平衡二叉树 (AVL Trees)

  平衡二叉树是一种特殊的二叉树，所以他也满足前面说到的二叉树的两个特性，同时还有一个特性：

它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

  大家也看到了前面[35 27 48 12 29 38 55]插入完成后的图，其实就已经是一颗平衡二叉树啦。
  那如果按照[12 27 29 35 38 48 55]的顺序插入一颗平衡二叉树，会怎么样呢？我们看看插入以及平衡的过程：

  这棵树始终满足平衡二叉树的几个特性而保持平衡！这样我们的树也不会退化为线性链表了！我们需要查找一个数的时候就能沿着树根一直往下找，这样的查找效率和二分法查找是一样的呢！
  一颗平衡二叉树能容纳多少的结点呢？这跟树的高度是有关系的，假设树的高度为h，那每一层最多容纳的结点数量为2(n-1)，整棵树最多容纳节点数为20+21+22+...+2^(h-1)。这样计算，100w数据树的高度大概在20左右，那也就是说从有着100w条数据的平衡二叉树中找一个数据，最坏的情况下需要20次查找。如果是内存操作，效率也是很高的！但是我们数据库中的数据基本都是放在磁盘中的，每读取一个二叉树的结点就是一次磁盘IO，这样我们找一条数据如果要经过20次磁盘的IO？那性能就成了一个很大的问题了！那我们是不是可以把这棵树压缩一下，让每一层能够容纳更多的节点呢？虽然我矮，但是我胖啊...
B-Tree

  这颗矮胖的树就是B-Tree，注意中间是杠精的杠而不是减，所以也不要读成B减Tree了~
  那B-Tree有哪些特性呢？一棵m阶的B-Tree有如下特性：
<blockquote>
1、每个结点最多m个子结点。
2、除了根结点和叶子结点外，每个结点最少有m/2（向上取整）个子结点。
3、如果根结点不是叶子结点，那根结点至少包含两个子结点。
4、所有的叶子结点都位于同一层。
5、每个结点都包含k个元素（关键字），这里m/2≤k