数据库的底层实现之B+树原理

用了这么久数据库做项目，那你知道数据是怎么存在数据库里吗？他们是如何存储的吗？

今天咱们就来扒一扒数据库的底层实现，数据库的底层大部分是由都是由B+树实现的，那为什么不是其他的数据结构呢，比如二叉树，链表或者其他呢？今天我们就来一探究竟。

思考下，数据库是如何存在磁盘上呢？
。
。
。
。
。
。
。

因为数据库是可以持久化的所以他一定是存储在硬盘上的，然而，从硬盘读取数据是相对内存来说是极度缓慢的，一次IO大概在9ms左右，它的成本大概是内存的10万倍。也正是因为磁盘IO的昂贵，所以操作系统对此做了优化，也就是预读；每一次可以读取一个数据时，他相邻的数据也一起读取出来。看一下原理，局部预读原理：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的数据，根据操作系统不同，一页是4k或者8k。也就是说，每读一页时，就发生了一次IO。
也正是因为磁盘有预读机制的缘故，所以才能有减少磁盘IO的可能性，先卖个官司。

磁盘的存储是线性内存地址（见图1）

硬盘是由很多的内存空间组成的，内存空间是连续的，内存空间包含两部分，第一部分是内存地址，第二部分是当前内存的值。

1.二分查找——非平衡二叉树
操作系统的内存是连续的存储的，寻址就是很耗时的，你可以把它理解成一个数组的，当我们对数组进行，查找的时候二分查找的速度应该是最快的，因为理论上每一次查找都能筛掉大概一半的无效的数据，二分查找就相当于非平衡二叉树查找，所以二分查找的速度会因为选择的中间变量的位置来决定。

如果极端情况，会造成n次查找(见图3)。因为数据库要求稳定性，即每一次查找的速度都还行。就好比如果你上某宝查询商品时，如果遇到一次这种情况，你就直接口吐芬芳了，随即怒卸之！所以为了让用户留下来，我们要让每次查找都差不多，所以就有了平衡二叉树。

2.平衡二叉树
平衡二叉树（常用算法实现有红黑树），顾名思义，就是每个节点的两边比较平衡，它的特征是根节点是空树，或者每个节点的左右子树的节点数相差不超过1，因为当每次添加一条数据时，他就会添加一个子节点，然后他会自旋转，把左右子树调整为差值小于等于1，即每次查找的次数都是log以2为底N的对数或者+1.因为所以，他的查找也比较稳定。因为一个箭头都是一次寻址过程，都比较耗时，并且如果总数据慢慢增多，查询效率下降的还是比较快。那怎么才能更快些呢？然后就有了B树。

3.B树
每个节点只存一节点显然已经不能更快了，那怎么办呢？
B树来了，B树就是N阶B树，N阶限制的是每个节点最多有N个子树。然后因为每个节点能存多个值，N阶B树的特点就是，每个节点最多有N个儿子节点，但是每个节点存多个值，通过每个节点存多个值，所以树变得更矮胖，也就是IO次数更少，更快的查找到。当删除节点11时，就会自动左旋，让树变得平衡，以此来减少对比的次数，保证查询的速度最快。


查询速度已经很快了，但是如果你要进行范围查询就比较麻烦了。
比如要做查询该值大于3并且小于13的数据，如果用B树查找是这样的（图7）
1.要先找到3所在的位置
2.找到13算在的位置
3.找到3以后的元素，在回退到上一层，看有没有右节点，再回退上一层，再看看有没有右节点。
4.一直到13的位置的左节点的位置。
Ps.看看我这个10来条数据，来一个范围查找最少最少要5次IO，IO是很昂贵的，所以就有了B+树。

4.B+树
B+树的特点是，所有data都存在叶子节点上，非叶子节点上不存data，只是做索引。然后叶子节点是一个连续的双向链表，树的深度没有增加，也就是查询速度没有变慢多少，但是它的范围查找时的速度是大大的提高。

来看一下B+树的范围查找，还是刚才的查找
要做查询该值大于3小于13的数据，用B+树查找的步骤
1.查找到3的位置，一直往后，查到13停止

what？这TM也太快了吧！只要找到3所在的节点，就基本不需要IO了，跟查询速度一样快！嗖嗖的！
总结
最后总结下，B+树是兼顾了查询的速度和范围查找的速度的终极产物，所以好多数据库的底层使用了B+树来实现。

今天是大年初五，慕容田雨祝大家新春快乐，万事如意，阖家欢乐，鼠年大吉！