B+ деревья

Элементарное введение на GeeksForGeeks [ссылка]

Хорошая статья с примерами [ссылка]

Лекция по древовидным индексам - университет Каролины [ссылка] - ISAM и B+деревья; картинки с коровами (?). Примечание: RID = row id, fanout - ветвление.

Коммуникации в распределённых системах

Французская лекция по групповым коммуникациям [ссылка]
Очень коротко по видам связей (упрямые, надежные) [ссылка]

LSM-деревья

SSтаблицы и LSM-деревья [ссылка] - статья Александра Межова

Владимир Кузнецов - о структурах данных в СУБД

Несколько видео Владимира Кузнецова на канале Сергея Немчинского
Про В-деревья [ссылка]; про LSM-деревья [ссылка]; про log-based [ссылка].

Алекс Петров (database internals)

Это такой совсем молодой парень из Мюнхена, который долго писал книгу Database internals и наконец написал. И её издал O'Reilly.

В поддержку книги он делал доклады на конференциях, писал статьи в интернете. Соответственно, часть его труда попала в открытый доступ. Даю ссылки:

Algorithms behind Modern Storage Systems [ссылка] - видеозапись доклада на конференции QCon2018 (размещена на Youtube канале InfoQ)

Блог Databasss на metium.com [ссылка] - B-деревья, LSM-деревья, немного о распределённых системах

Доказательство FLP

Оно было опубликовано в 1983 году в статье Impossibility of Distributed Consensus with One Faulty Process [ссылка]. 

В более доступной форме его можно найти в:

A Brief Tour of FLP Impossibility [ссылка] - статья

The FLP Proof [ссылка] - ролик на Youtube

Кстати, нашёл конспект лекций по распределенным алгоритмам знаменитой Нэнси Линч, одного из авторов FLP [ссылка]

История распределенных систем

Вводная лекция (Introduction to Distributed Systems) из курса Андреа Омичини [ссылка] - опирается на книгу Таненбаума

A Thorough Introduction to Distributed Systems - текст с DataCamp [ссылка]. Быстренько пробежались по HDFS, BitTorrent, blockchain.

Короткая вводная лекция из курса Г.Као [ссылка] - схематическая информация.

Статья The Evolution of Distributed Systems с DZone [ссылка] - виртуальные машины, Docker, Kubernetes

Заметки Аспнеса по теории распр систем

Обнаружил объёмистый труд за авторством Джеймса Аспнеса. Аж 484 страницы. Называется почему-то notes - заметки. Полное название Notes on Theory of Distributed Systems [ссылка], лежит на сайте Йеля.

Разбито на три части - передача сообщений, общая память и другие коммуникационные модели. Есть Паксос. Что ещё интереснее - кроме часов Лэмпорта есть часы Найгера-Туэга-Уэлша, которых я вообще нигде больше не встречал. Так что буду читать.

История СУБД

Небольшой текст A Timeline of Database History [ссылка]. В конце есть источники, можно пройти по гиперссылкам и найти побольше информации.

Реферат по истории СУБД [ссылка]

А вот статья History Of Databases [ссылка] на researchgate. Пока не читал.

СУБД с нуля

Некий товарищ решил разобраться, как работает СУБД, путём написания игрушечной копии SQLite. Получилось отличное руководство (с кодом), в котором раскрываются многие детали. Есть про B-деревья. Вот [ссылка] на оглавление.

B-деревья

Вот, кстати, еще про дендритов.

B-деревья -- одна из самых используемых в области СУБД структур данных. Применяется как для хранения таблиц, так и для индексов.

Статьи
R. Bayer, C. McReight Organization and maintenance of large ordered indices // Acta Inf. 1, 3 (1972), 173- 189 [ссылка] - похоже, оригинал 

D.Comer The Ubiquitous B-Tree [ссылка]  - разбор "для маленьких", есть про модификации B-деревьев

Видео на YouTube
B-Tree Indexes [ссылка] - коротенькое введение с картинками
File Systems 1: File Indexes with B-Trees [ссылка] - много примеров на вставку и удаление

Посты
How Database B-tree Indexing works [ссылка] - самое полезное из того, что я нашел; конкретно показано, как хранить таблицы и индекс в B-дереве

В-деревья в блоге stalinko[ссылка] - кратко об алгоритмах, небольшие примеры


Лекции
Лекция М.Курносова [ссылка] - очень обстоятельно о предмете

Indexing [ссылка] - лекция из курса Database Systems [ссылка на курс] университета Южной Калифорнии; про индексы вообще и B-tree индексы в частности

Лабораторная работа по B-деревьям [ссылка] - хорошие примеры на вставку, удаление

Студопедия про B-деревья [ссылка] - тоже есть примеры

Деревья

Я про структуру данных. Насколько же важны и разнообразны деревья в информатике! Сколько там разных интересных идей и алгоритмов.

На GeeksForGeeks есть отдельная категория статей про деревья. Вот [ссылка], например, текст о распечатке двоичного дерева (здесь его на бок кладут). А сбоку - ссылки на другие статьи о "древесных" алгоритмах. Читать - не перечитать.

Как СУБД хранят данные на диске

На канале InfoQ нашёл лекцию о двух структурах данных, которые используются в СУБД [ссылка на видео].

Первая - неизменяемая (immutable, данные только дописываются), называется log-structured merge-tree (LSM-tree). Попробую перевести как лог-структурированное дерево слияний. Или просто LSM-дерево. Используется в HBase, Cassandra. Докладчик сослался на статью The Log-Structured  Merge-Tree  (LSM-Tree)
[ссылка].

Вторая - изменяемая (mutable). Это знаменитые B-деревья. Ссылка на статью The Ubiquitous B-Tree [ссылка].

В конце приводится статья о гипотезе RUM. Это очередной треугольник типа CAP-теоремы. Рассматривается три параметра: количество чтений (R),  стоимость обновления (U) и накладные расходы по памяти (M). И дается утверждение: попытка оптимизировать любые два параметра приводит к ухудшению третьего параметра. Статья называется Designing Access Methods: The RUM Conjecture [ссылка]