Зачем использовать дерево B для индекса базы данных, отличного от дерева AVL

Question

Я слышал некоторые утверждения, такие как, учитывая высоту дерева AVL и максимальные ключи, которые может содержать узел дерева AVL, поиск дерева AVL будет занимать много времени из-за диска io.Однако представьте, что индексный файл содержит всю древовидную структуру AVL, и тогда размер индексного файла меньше размера вентилятора, мы можем просто прочитать все AVL-дерево только за один раз на диске io.

Кажется, что использование дерева AVL не приводит к дополнительному дисковому вводу, как объяснить, что дерево B лучше?

Answer 1

мы можем просто прочитать все дерево AVL всего за один диск io

Да, это может работать так.По сути, вся структура данных будет занесена в память.IO больше не будет проблемой.

Некоторые базы данных используют эту стратегию.Например, SQL Server In-Memory «Hekaton» делает это и обеспечивает ~ 100-кратную нормальную пропускную способность для OLTP.

Hekaton использует две структуры данных индекса: хеш-таблицы и деревья.Я думаю, что деревья называются cw-деревьями и похожи на b-деревья.

Для рабочих нагрузок базы данных общего назначения очень желательно, чтобы все в памяти не требовалось.В этих случаях B-деревья - отличный компромисс в дизайне.

Answer 2

В базах данных используются сбалансированные бинарные деревья (плюс). Avl является лишь частным случаем этих сбалансированных деревьев, поэтому в этом нет необходимости