B树、B+树
AI摘要: 本文探讨了B树和B+树在数据结构中的应用，特别是在处理大量数据和进行高效查询时的优势。首先，文章指出平衡二叉树虽然简单但不适合处理海量数据，因为其高度限制导致磁盘IO次数增多。接着，B树通过在每个节点内部排序来提高读取速度，而B+树则通过将数据存放在叶子节点中并使用链表连接所有叶子节点来减少磁盘IO次数，同时保证查询速度的稳定性。最后，文章提供了参考资料链接，供有兴趣深入了解的读者参考。
这三棵树在数据结构课、操作系统课、数据库课上都讲过几遍，奈何一次都没听到脑子，考试不考就不学，考完就忘，现在来还一还欠下的债。
在没有学习B树之前，想要完成高效的数据查询的数据结构就是平衡二叉树，通过左右子树的高度差限制小于1，使得查询时间复杂度平均在O(logN)。
那么为什么不直接使用平衡二叉树呢？这是考虑到保存百万级别海量数据的数据库场景下，平衡二叉树力不从心。
-
首先大量的数据带来的磁盘IO问题：由于所有数据不可能直接放到内存当中，数据索引和数据本身都是记录在磁盘上面的，而磁盘是一个慢到离谱的设备。所以平衡二叉树的高度绝对不能太高，必须足够矮才能减少磁盘IO次数。
-
此外，查询数据的时间必须足够稳定。在平衡二叉树中，如果是在树根就查询到数据，此时需要1次磁盘IO；如果是在树底查询到数据，那么需要进行O(logN)次磁盘IO。
-
最后是范围查询问题。数据库肯定得支持范围查询，在平衡二叉树中，想要查找[a, b] 范围的所有数据，就需要在这个区间进行中序遍历，这会导致大量磁盘IO。
B树
B树解决了读取速度慢的问题。
要想压低树的高度，就只能在每个节点里面多塞数据和索引，这样就形成了一个多叉树，每个节点内部是排序好的。
B+树
B+树解决了B树的查找速度不稳定和范围查找速度慢的问题。
那么为了每次查询速度稳定，并且尽量减少磁盘IO次数，可以把所有的数据存放在最底层，也就是叶子节点中，这是B+树的一个重要特点。由于叶子节点才存放数据和索引，非叶子节点只存放索引。所以，非叶子节点就有更多空间来存放更多的索引，从而更加明显地减少树的高度，减少磁盘IO次数
如果想要实现范围查找，那么在B+树中，可以通过链表连接所有的叶子节点。