第三堂数据结构课：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ₘ(X1)也就是树高H约等于log以M为底X的对数。这里的M是个常数介于K/2和K之间所以在大数据量下时间复杂度就是O(logN)底数的差异可以忽略。推完这个公式我才理解为什么老师说B树矮胖——树高只和节点能容纳的子节点数量有关和数据总量是对数关系。B树非叶子节点只存Key推完B树的时间复杂度接下来讲B树。老师用构建一棵5阶B树的过程来演示。B树和B树最核心的区别是B树的非叶子节点只存Key索引不存Value数据。这就意味着同样大小的磁盘页比如4KBB树的每个节点能容纳更多的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 100B树找到id1的位置然后顺着链表往后走99步就行了。B树想做范围查询得反复从根节点开始找效率低得多。所以MySQL的InnoDB引擎用B树作为索引结构不是没有原因的。一点补充课后待办里有一条是预习JVM内存图绘制看来下节课的方向可能是从磁盘存储切回到内存结构了。数据结构这条路从数组到B树从内存到磁盘逻辑主线越来越清晰了。这节课最让我有收获的还是那个等比数列推导——以前背时间复杂度都是死记硬背这次是自己推出来的感觉完全不一样。