Одна из лучших книжек по алгоритмам, которые я когда-то либо читал. Избранные моменты:

  • В во второй главе разобраны основные противоречия построения СД: чтение, обновление, компактность в памяти, а также точечные/интервальные запросы, вставка и удаление.
  • Далее идет теория и практика, которые позволяют по характеру и последовательности операций выбрать СД. Например, когда нужно использовать B+-дерево, а когда префиксное? Полезен ли фильтр Блума для LSM-деревьев?
  • В главе 4.11 приведены примеры продуктов, в которых используются “сложные” деревья — это не какая-то экзотика, а вполне популярные вещи.
  • В главе 6.1 — чем отличаются традиционные от колоночных СУБД, и для каких сценариев какие лучше?
  • В 6.2 — какие СД используются внутри файловых систем.
  • В 6.3 — что там у ML?
  • Новому времени — новые типы запросов: “глубокое” удаление для GDPR и какие это несет последствия для СД.
  • Ну и железо не отстает, оно разумеется влияет на построение СД (правда тут скорее обзор статей на тему).

В конце сделан вывод, что создание СД — это искусство. Возможных структур данных — больше чем 10^100.

Рекомендую к прочтению тем, кто работает с большими данными/СУБД. Но вообще довольно познавательно для всех разработчиков.