I'm just wondering why the kd-tree is always considered as a main memory structure. This means that every node is kept in main memory, doesn't it?
我只是想知道为什么kd树总是被认为是主存储器结构。这意味着每个节点都保存在主内存中，不是吗？
Compared to B-trees (where every node should fit into one disk block), this doesn't make too much sense to me. Could anyone explain that? Thanks :)
与B树（每个节点应该放入一个磁盘块）相比，这对我来说没有多大意义。有人可以解释一下吗？谢谢 ：）
1 个解决方案
#1
1
To efficiently store the tree on the disk, it should fit into 8k pages (the page size of most harddrives). With a k-d-tree this would be enormous waste, and very inefficient.
为了有效地将树存储在磁盘上，它应该适合8k页（大多数硬盘的页面大小）。使用k-d树，这将是巨大的浪费，并且非常低效。
Thus, writing the k-d-tree to disk doesn't pay off.
因此，将k-d-tree写入磁盘并不能带来回报。
B-trees on the other hand can be set up so that they use the whole disk page. This is important, because disks are more efficient when accessing blocks (or even better: ranges of blocks), not when randomly accessing bytes.
另一方面，可以设置B树，以便它们使用整个磁盘页面。这很重要，因为磁盘在访问块时更有效（甚至更好：块的范围），而不是在随机访问字节时。
#1
1
To efficiently store the tree on the disk, it should fit into 8k pages (the page size of most harddrives). With a k-d-tree this would be enormous waste, and very inefficient.
为了有效地将树存储在磁盘上，它应该适合8k页（大多数硬盘的页面大小）。使用k-d树，这将是巨大的浪费，并且非常低效。
Thus, writing the k-d-tree to disk doesn't pay off.
因此，将k-d-tree写入磁盘并不能带来回报。
B-trees on the other hand can be set up so that they use the whole disk page. This is important, because disks are more efficient when accessing blocks (or even better: ranges of blocks), not when randomly accessing bytes.
另一方面，可以设置B树，以便它们使用整个磁盘页面。这很重要，因为磁盘在访问块时更有效（甚至更好：块的范围），而不是在随机访问字节时。