Мне просто интересно, почему kd-дерево всегда считается основной структурой памяти. Это означает, что каждый узел хранится в основной памяти, не так ли?
По сравнению с B-деревьями (где каждый узел должен помещаться в один дисковый блок) это не имеет для меня особого смысла. Кто-нибудь может это объяснить? Спасибо :)
Чтобы эффективно хранить дерево на диске, оно должно умещаться в 8k страниц (размер страницы большинства жестких дисков). С k-d-деревом это было бы огромной тратой и очень неэффективно.
Таким образом, запись k-d-дерева на диск не окупается.
С другой стороны, B-деревья можно настроить так, чтобы они использовали всю страницу диска. Это важно, потому что диски более эффективны при доступе к блокам (или даже лучше: к диапазонам блоков), а не при случайном доступе к байтам.
