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?
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 :)
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.
Thus, writing the k-d-tree to disk doesn't pay off.
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.