Многие (возможно, большинство?) Приложения баз данных сегодня используют B-деревья и варианты для хранения данных, потому что эта структура данных оптимизирует операции чтения, записи и поиска на жестком диске (и эти операции, в свою очередь, играют важную роль в общей эффективности базы данных).
Должны ли твердотельные накопители (SSD) полностью вытеснять традиционные жесткие диски (HDD), однако можно ли сказать, что B-деревья и их варианты устареют, предоставляя место для структур данных, которые более эффективно работают с памятью прямого доступа? Если так, то какими будут эти структуры? (например, хеш-таблицы, деревья AVL)
database
data-structures
Даниэль Скокко
источник
источник
Ответы:
B-деревья чаще всего используются для индексов базы данных на жестком диске, но они имеют преимущества даже в виде структуры данных в памяти, учитывая современную иерархию памяти с несколькими уровнями кэша и с виртуальной памятью. Даже если виртуальная память находится на SSD, это не изменится.
Я использую многоканальную древовидную библиотеку в стиле B + в памяти, которую я довольно много написал на C ++. У него могут быть преимущества в производительности - причина, по которой он был изначально написан, заключался в том, чтобы попытаться использовать кеш лучше, - но я должен признать, что часто это не работает. Проблема заключается в компромиссе, который означает, что элементы должны перемещаться внутри узлов при вставках и удалениях, чего не происходит для двоичных деревьев. Кроме того, некоторые из низкоуровневых хакерских кодов, которые я использовал для его оптимизации - ну, они, вероятно, сбивают с толку и побеждают оптимизатора, по правде говоря.
В любом случае, даже если ваши базы данных хранятся на SSD, это еще блочно-ориентированное устройство хранения, и все еще есть преимущество в использовании B-деревьев и других многопоточных деревьев.
НО около десяти лет назад были изобретены алгоритмы и структуры данных, не обращающие внимания на кеш. Они не обращают внимания на размер и структуру кэшей и т. Д. - они (асимптотически) наилучшим образом используют любую иерархию памяти. B-деревья должны быть «настроены» на определенную иерархию памяти, чтобы наилучшим образом их использовать (хотя они работают довольно хорошо для довольно широкого диапазона вариаций).
Забытые в кеше структуры данных еще не часто встречаются в дикой природе, если они вообще есть, но сейчас они могут сделать обычные двоичные деревья в памяти устаревшими. И они также могут оказаться полезными для жестких дисков и твердотельных накопителей, так как им все равно, какой размер страницы у кластера или размер кеша жесткого диска.
Макет Ван Эмда Боаса очень важен в структурах данных, не обращающих внимания на кэш.
Курс по алгоритмам MIT OpenCourseware включает в себя некоторый охват структур данных, забывающих о кеше.
источник
Априори, да, большинство механизмов баз данных придется переписывать, так как B-Tree больше не будет самой эффективной структурой данных для хранения данных, учитывая, что локальность важна для жесткого диска, где диск перемещается медленно и данные извлекаются в блоках, что означает, что любое изменение данных должно:
Это 10 + 3 + 3 + 10 + 3 + 3 = 34 мс
В среднем выполнение одного и того же на SSD составляет всего 1 мс, независимо от положения на диске.
А поскольку хеш-таблица намного быстрее, мы могли бы подумать, что она будет лучшей заменой.
Единственная проблема состоит в том, что хеш-таблицы не сохраняют порядок, и, следовательно, невозможно найти следующий и предыдущий, как это делает Ван Эмде Боас.
Видеть:
Почему важно найти следующее и предыдущее? Представьте, что вы получаете все элементы больше x и меньше z, вам нужно использовать индексы с find previous и find next.
Ну, единственная проблема в том, что мы не нашли хеш-таблицы со способностями сохранения порядка. Возможно, размер корзины в B-дереве будет важен, но это решается с помощью алгоритмов, не обращающих внимания на кэш.
Так что я бы сказал, что это проблема открытого типа.
источник