如题。这里我们可以分析一下在数据库中，使用B+树做查询时，时间复杂度是怎样的。
先说结论。
综合看网上各种帖子，总结得出以下结论：
$O(m\log_mN)$、$O(\log_2m\log_mN)$、$O(\log_mN)$、$O(\log N)$
以上这些都是正确的。
从以下两个方面来做讨论。
-
一般意义上的时间复杂度，仅考虑算法在计算上消耗的步骤，不考虑IO
a. B+树搜索时间复杂度 = 搜索时访问的节点数量 * 节点的搜索时间复杂度
b. 访问的节点数量 = B+树深度 =$\log_mN$
c. 每个节点有m个数据，那么节点内的搜索时间复杂度：
基于数组/链表的线性搜索 = $O(m)$
基于数组的二分搜索 = $O(\log_2m)$
d. 因此，B+树搜索时间复杂度 = $\log_mN \times O(m)$或者$\log_mN \times O(\log_2m)$，即$O(m\log_mN)$或$O(\log_2m\log_mN)$.
e. 另外，$\log_2m\log_mN$可以继续化简，步骤如下：
为什么可以设$m=2^x$,m在这里就是大于2的自然数，这句话其实就是问$2^x$能不能表示任意一个大于2的自然数。当然是可以的，因为$2^x$是一条大于0的连续曲线。 所以，在内存中，B+树在一个节点内也采用二分法查找元素（最快的方式了），B+树和二叉树的时间复杂度都是$O(\log_2{N})$,即在内存中（不考虑磁盘IO的特殊性），N叉树的查询时间复杂度都是$O(\log_2{N})$。
然后，你就会发现，越想越对，上学的时候，数据结构的课程上，老师教过用二叉树表示多叉树，现在一想，确实如此。其实想想，多叉树中，在寻找多个叉的过程中，如果采用了二分查找，不就是二叉搜索树吗？相当于“多叉”的搜索，变成了子树，这棵子树是二叉搜索树了，所以时间复杂度是$O(\log_2{N})$就太正常了。
-
B+ 树主要用在数据库、文件系统上，对于这种使用场景，IO 最耗费时间，执行几条指令、多访问几个节点没关系，但是多几次 IO 那时间是疯狂上涨（机械磁盘寻道时间是ms级，如果访问一个数据就要一次IO，那 B+ 树的搜索时间就直接炸了），B+树为什么要设计成矮胖的形状？为什么非叶子节点不存数据？都是为了减少IO次数。所以在实际工程中，我们讨论B+树的搜索时间复杂度，其实讨论的是磁盘 IO 次数。那么，磁盘IO次数怎么计算呢，它和B+树的 m和N 有什么关系？
| 
发表于 2023-11-13 23:39
|
发表于 2023-11-14 12:20
然而 学渣没看懂...