为什么kd树是主内存结构？

Question

我只是想知道为什么kd树总是被认为是一种主要的内存结构。这意味着每个节点都保存在主内存中，不是吗？

与B树(每个节点都应该放在一个磁盘块中)相比，这对我来说没有多大意义。有人能解释一下吗？谢谢:)

Answer 1

为了有效地将树存储在磁盘上，它应该适合8k页(大多数硬盘的页大小)。如果有一棵k-d树，这将是巨大的浪费，而且效率很低。

因此，将k树写入磁盘并不会有任何效果。

另一方面，可以设置B树，以便它们使用整个磁盘页。这一点很重要，因为磁盘在访问块(甚至更好:块的范围)时效率更高，而不是当随机访问字节时。