Ответ 1
Основным преимуществом дерева B + (и B-деревьев вообще) над двоичными деревьями поиска является то, что они хорошо работают с кешами. Если у вас есть двоичное дерево поиска, чьи узлы хранятся в более или менее случайном порядке в памяти, то каждый раз, когда вы следуете указателю, машине придется вытащить новый блок памяти в кэш процессора, что значительно медленнее, чем доступ к памяти уже в кеше.
B + -tree и B-tree работают, имея каждое node хранили огромное количество ключей или значений и имеют большое количество детей. Они обычно упаковываются вместе таким образом, чтобы один node мог хорошо вписываться в кеш (или, если он был сохранен на диске, вытаскивался с диска в одной операции чтения). Затем вам нужно сделать больше работы, чтобы найти ключ в node или определить, какой из них следует читать дальше, но поскольку все обращения к памяти, выполненные на одном node, могут выполняться без возврата на диск, время доступа очень маленький. Это означает, что, хотя в принципе BST может быть лучше с точки зрения количества обращений к памяти, B + -tree и B-tree могут работать лучше с точки зрения времени выполнения этих обращений к памяти.
Типичный пример использования B + -tree или B-tree находится в базе данных, где имеется огромное количество информации, и данные настолько многочисленны, что они не могут вписаться в основную память. Соответственно, данные затем могут быть сохранены в B + -tree или B-дереве на жестком диске где-нибудь. Это сводит к минимуму количество считываемых дисков, необходимых для поиска данных во время поиска. Некоторые файловые системы (например, ext4, я полагаю) также используют B-деревья по той же причине - они минимизируют количество требуемых обращений к диску, что является настоящим узким местом.
Надеюсь, это поможет!