CODEWITHSUNDEEP
databaseindexingtreekdtree
l3moony
l3moony

Reputation: 75

Why is the kd-tree a main memory structure?

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 :)

Upvotes: 1

Views: 242

Answers (1)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

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.

Upvotes: 2

Related Questions