Как работают индексы в базах данных: B-tree и LSM-tree

Поиск в сбалансированном бинарном дереве занимает логарифмическое время, а это теоретический предел. Не существует алгоритмов поиска сравнением, которые работали бы быстрее. Но для базы данных такое дерево всё равно слишком медленное. Разгадка этого парадокса кроется не в алгоритме, а в железе, и учебники обычно это упускают. В этом видео мы с нуля строим индекс базы данных и смотрим, как каждое ограничение железа меняет структуру данных. 0:00 Вступление: почему бинарные деревья не используются в базах данных 1:19 Бинарное дерево поиска и логарифмическая сложность 5:11 Бинарное дерево на диске 15:52 B-дерево (B-tree) 26:15 B+ дерево (B+ tree): диапазоны и индексные узлы 30:38 Запись и устройство SSD 35:57 LSM-дерево (LSM tree): MemTable, write-ahead log и SSTable 42:33 Фильтр Блума (Bloom filter) 51:05 Skip list 1:00:16 Compaction: слияние SSTable 1:02:09 Итоги: B-дерево или LSM-дерево и где они используются