第三堂数据结构课：B树的时间复杂度，原来是用等比数列推出来的

第三堂数据结构课：B树的时间复杂度，原来是用等比数列推出来的

上节课老师提到B树时只是引了个头，说"后续会细讲"。今天这堂课就是专门讲B树和B+树的，而且一上来就直接推导时间复杂度，数学公式铺了半个黑板。

说实话看到公式的那一刻我是有点慌的，但跟着推完之后发现，其实没有想象中那么复杂。

B树时间复杂度：等比数列求和

课程开始，老师直接抛出一个问题：B树的时间复杂度真的是O(logN)吗？如果是，这个log的底数是多少？

有同学说"不就是logN吗"，老师说那我们来推一下。

推导的核心是最矮情况分析。B树为了保证平衡，规定了节点子节点数量的上下限。以5阶B树为例：

• 非根节点最多5个子节点
• 非根节点最少3个子节点（K/2向上取整）

刚分裂完的节点，子节点数量恰好处于最少状态（3个），这是推导树高的关键。

假设每个节点有M个子节点，那么：

• 第1层：1个节点
• 第2层：M个节点
• 第3层：M²个节点
• 第H层：M^(H-1)个节点

每个节点存M-1个数据，总数据量 X = (1 + M + M² + … + M^(H-1)) × (M-1)

括号里是等比数列，求和得 (M^H - 1)/(M - 1)，再乘以(M-1)，化简为 X = M^H - 1。

所以 H = logₘ(X+1)，也就是树高H约等于log以M为底X的对数。

这里的M是个常数（介于K/2和K之间），所以在大数据量下，时间复杂度就是O(logN)，底数的差异可以忽略。

推完这个公式，我才理解为什么老师说B树"矮胖"——树高只和节点能容纳的子节点数量有关，和数据总量是对数关系。

B+树：非叶子节点只存Key

推完B树的时间复杂度，接下来讲B+树。老师用构建一棵5阶B+树的过程来演示。

B+树和B树最核心的区别是：B+树的非叶子节点只存Key（索引），不存Value（数据）。

这就意味着同样大小的磁盘页（比如4KB），B+树的每个节点能容纳更多的Key，子节点数量更多，树高更低。而B树每个节点既要存Key又要存Value，能容纳的Key数量就少了。

另一个关键区别是：B+树的所有叶子节点通过指针连成一个有序链表。这意味着做范围查询的时候，找到一个起点，顺着链表往后走就行了。

老师演示了B+树的插入过程——和B树类似，节点满了就分裂，中间Key上浮到父节点，但数据本身保留在叶子节点。所以B+树的叶子节点存了所有的数据，非叶子节点只是"路标"。

B树 vs B+树：谁用在哪儿

这是今天最有价值的对比部分，直接对应实际应用场景。

B树适合文件系统

B树的节点同时存Key和Value，查询的时候如果在非叶子节点就命中了，直接返回，不需要走到叶子节点。这在磁盘场景下意味着减少了IO次数。文件系统的目录结构、ext4文件系统都用B树。

B+树适合数据库索引

B+树必须遍历到叶子节点才能拿到数据，看起来好像比B树慢？但实际上：

第一，B+树的非叶子节点不存Value，所以单页能容纳的Key更多，树高更低，整体IO次数反而更少。

第二，叶子节点的链表结构让范围查询极其高效。比如SQL里的SELECT * FROM table WHERE id BETWEEN 1 AND 100，B+树找到id=1的位置，然后顺着链表往后走99步就行了。B树想做范围查询，得反复从根节点开始找，效率低得多。

所以MySQL的InnoDB引擎用B+树作为索引结构，不是没有原因的。

一点补充

课后待办里有一条是"预习JVM内存图绘制"，看来下节课的方向可能是从磁盘存储切回到内存结构了。数据结构这条路，从数组到B+树，从内存到磁盘，逻辑主线越来越清晰了。

这节课最让我有收获的还是那个等比数列推导——以前背时间复杂度都是死记硬背，这次是自己推出来的，感觉完全不一样。