Вводная лекция (Introduction to Distributed Systems) из курса Андреа Омичини [ссылка] - опирается на книгу Таненбаума
A Thorough Introduction to Distributed Systems - текст с DataCamp [ссылка]. Быстренько пробежались по HDFS, BitTorrent, blockchain.
Короткая вводная лекция из курса Г.Као [ссылка] - схематическая информация.
Статья The Evolution of Distributed Systems с DZone [ссылка] - виртуальные машины, Docker, Kubernetes
вторник, 20 августа 2019 г.
Заметки Аспнеса по теории распр систем
Обнаружил объёмистый труд за авторством Джеймса Аспнеса. Аж 484 страницы. Называется почему-то notes - заметки. Полное название Notes on Theory of Distributed Systems [ссылка], лежит на сайте Йеля.
Разбито на три части - передача сообщений, общая память и другие коммуникационные модели. Есть Паксос. Что ещё интереснее - кроме часов Лэмпорта есть часы Найгера-Туэга-Уэлша, которых я вообще нигде больше не встречал. Так что буду читать.
Разбито на три части - передача сообщений, общая память и другие коммуникационные модели. Есть Паксос. Что ещё интереснее - кроме часов Лэмпорта есть часы Найгера-Туэга-Уэлша, которых я вообще нигде больше не встречал. Так что буду читать.
История СУБД
понедельник, 19 августа 2019 г.
СУБД с нуля
Некий товарищ решил разобраться, как работает СУБД, путём написания игрушечной копии 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-деревья [ссылка] - тоже есть примеры
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-деревья [ссылка] - тоже есть примеры
суббота, 17 августа 2019 г.
Деревья
Я про структуру данных. Насколько же важны и разнообразны деревья в информатике! Сколько там разных интересных идей и алгоритмов.
На GeeksForGeeks есть отдельная категория статей про деревья. Вот [ссылка], например, текст о распечатке двоичного дерева (здесь его на бок кладут). А сбоку - ссылки на другие статьи о "древесных" алгоритмах. Читать - не перечитать.
На GeeksForGeeks есть отдельная категория статей про деревья. Вот [ссылка], например, текст о распечатке двоичного дерева (здесь его на бок кладут). А сбоку - ссылки на другие статьи о "древесных" алгоритмах. Читать - не перечитать.
пятница, 16 августа 2019 г.
Как СУБД хранят данные на диске
На канале 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 [ссылка]
Первая - неизменяемая (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 [ссылка]
Подписаться на:
Сообщения (Atom)