做完了cmu 15-445 2020的project之后，想着稍微归纳一下从这个项目里学到的东西，这个项目总共完成了缓存管理、b+树索引、executor、transaction manager+lock manager 等组件，也让我对数据库的基本组件有了一定的了解。主要想记录两部分内容：一个是这系列里的b+树索引，另一个是事务部分。但是目前对事务还不够熟悉，之后看情况再说吧。另外在后续自己的学习过程中，关于sql解析的部分也做了一点尝试，如果有机会也想再完善然后归纳一下。本文其实也是在回答我刚学习b+树时提出的疑问。水平所限，文中多半存在纰漏，请保持怀疑的态度阅读。
文章的开始，我们先提出几个问题：
- 什么是b+树？
- b+树要在什么场景下使用，使用它的优势是什么？
- 它的替代品有什么？
首先，什么是b+树。b+树本质上是一种平衡搜索树，所以首先它是：1).搜索树，b+树节点满足左子树的值总是小于等于右子树（非空时），可以快速查找某个值是否存在。2).平衡树，这意味着b+树每条路径的长度都基本相同，查找的平均时间复杂度为$O(logN)$。不过与AVL树中定义平衡的概念为左右子树高度相差不大于1不同的是，b+树实际上任何节点的左右子树高度都是一致的，始终是平衡的（如果某个节点元素过多会进行分裂，过少会进行重新分配或者合并）。
那么，具有以上性质的b+树，应用场景是什么呢。想想平衡二叉树我们一般用来做什么，平衡二叉树的优点是查找快，所以一般都用在查找操作比较多的地方。我们灵机一动，联想到从数据库系统中读取数据恰好需要在大量数据中进行查找，那么b+树不是恰好就能作为数据库的索引来使用了嘛。于是我们为b+树买到了合适的岗位，即刻走马上任鹅城。
但是为什么我们数据库的索引喜欢用b+树而不是其他的平衡二叉树比如AVL树或红黑树呢。这就要涉及到b+树和其它平衡二叉树在维护树的结构以及查找时的区别了。以AVL树为例，AVL树中每个节点都代表一个值，这样导致 value 相近的节点可能分布在横跨叶节点到根节点的整个路径上，它们在内存中不一定会分配在相邻的页面，这时进行一个小范围的查询都可能会读取若干个页面；另外AVL树很容易产生失衡，需要大量的旋转操作。在内存中时上述两个问题都不是事，但是场景移到磁盘上就大不一样。现在 DDR4 内存读取的速度约为10GB/s，而机械硬盘的读取速度约为 120MB/s，哪怕是固态硬盘也只能达到 500MB/s 左右（数据均为顺序读的场景，暂无严谨考证，仅供参考），相差几乎2个数量级，使用AVL树每次都会产生大量的跨页访问，需要多次IO操作，在这种情况下主要瓶颈基本就变为磁盘IO的开销了。
既然我们已经说了AVL树作为索引会产生大量IO而不适合，那么已经被广泛应用为索引的b+树应该就是在这方面作出改善了。它的数据全部放在叶节点中（一个节点对应一个page，因此一个叶节点可以存放多个值），这样 value 相近的元素在物理存储上的位置也大概率在靠在一起；同时允许节点为半空的（即最少允许只存放 $ \lceil n/2 \rceil $个元素），减少了插入/删除节点时对树结构的调整，也就大量减少了磁盘IO；最后还有一点是，前面提到的平衡树都是二叉树，而b+树的分支通常远大于2,每个内部节点可能拥有几十到上千子节点，这使得b+树的高度更低，从根节点到叶节点路径更短，也就意味着一次查找需要的IO次数也更少。以上就是b+树作为数据库索引的优势，在读写均衡的场景下b+树有着很不错的表现，因此也是目前数据库采用最为广泛的索引结构。
// TODO：原始论文 conclusion
最后，数据库索引除了可以用b+树，有没有其他形式的索引结构。当然是有的，这里搬运「数据库系统概念」上的例子，我们可以做顺序索引、多级索引、哈希索引（比如MySQL使用Memory引擎时可选择 Hash Index）等，另外还有 levelDB 中实现的 LSM 索引，适用于写多读少的场景，以后也许会深入介绍。
接下来我们会先介绍b+树的插入、删除等基本操作，然后介绍如何保证b+树并发访问时的正确性，敬请期待:P。
To Be Continued…