Когда бинарное дерево лучше, чем B-Tree?

Question

При хранении двоичного дерева или B-дерева на вторичном устройстве хранения, таком как диск или лента, имеет ли бинарное дерево преимущество перед B-деревом?

Меня спрашивали по заданию «Когда у B-Trees есть преимущество перед бинарными деревьями?»

Что я понял, так это то, что B-Tree лучше, потому что для этого требуется менее частый доступ к диску (читает больше данных на доступ к каждому узлу) и переходит на меньшее количество узлов, чтобы добраться до конечного узла. Но, как формулируется вопрос, это означает, что существует точка, в которой бинарное дерево действительно имеет преимущество перед B-деревом. Итак, is там точка, когда бинарное дерево лучше (более эффективно), чем B-Tree, когда они хранятся на вторичном хранилище?

Answer 1

Неправильно сравнивать отсортированное дерево (B-дерево) и простое двоичное дерево, они не равны. Поэтому я предполагаю, что вы имеете в виду двоичное дерево поиска.

B-Tree был разработан, чтобы быть эффективным, когда данные хранятся на относительно медленном хранении. Например, когда вы загружаете или сохраняете данные из файловой системы с размером кластера 4kb, неважно, сколько данных в этом диапазоне 0..4kb вам нужно, потребуется 1 байт или 4 килобайта, и это действительно займет время. B-дерево учитывает этот факт и использует его. Таким образом, во всех нормальных/общих сценариях использования будет более эффективно использовать B-дерево (с точки зрения используемого пространства и производительности).