Вот, кстати, еще про дендритов.
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-деревья [ссылка] - тоже есть примеры
понедельник, 19 августа 2019 г.
суббота, 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 [ссылка]
четверг, 16 мая 2019 г.
Ссылки: браузеры и компиляторы
понедельник, 6 мая 2019 г.
Ставим Zookeeper и Kafka на Ubuntu
На эту тему есть масса информации в Интернете, но всё как-то не мог найти подхдящее описание - то слишком коротко, то вообще устаревшие сведения.
В итоге остановился на статье Zookeeper & Kafka Install с ресурса BogoToBogo. Вполне себе доходчиво и наглядно.
Интересно, что везде Zookeeper рассматривается как основа для Kafka. Такое впечатление, что больше нигде Смотритель зоопарка и не применяется:)
четверг, 11 апреля 2019 г.
Как обрушить программу на C++
Пытаемся выйти за пределы массива и получить segfault:
int *p = new int[3];
p[100] = 100;
Компилируем g++. Ничего не происходит. А все потому, что тут undefined behaviour, компилятор имеет право разбираться с проблемой как хочет. Вот тут об этом подробно (Accessing an array out of bounds gives no error, why?).
Делим на 0:
int x = 1/0;
Опять ничего! Программа компилируется, запускается.
Попробуем создать массив из минус одного элемента:
int *p = new int[-1];
Компилятор проглатывает без проблем. Но при запуске получаем исключение bad_alloc. Ура! Программа грохнулась!
int *p = new int[3];
p[100] = 100;
Компилируем g++. Ничего не происходит. А все потому, что тут undefined behaviour, компилятор имеет право разбираться с проблемой как хочет. Вот тут об этом подробно (Accessing an array out of bounds gives no error, why?).
Делим на 0:
int x = 1/0;
Опять ничего! Программа компилируется, запускается.
Попробуем создать массив из минус одного элемента:
int *p = new int[-1];
Компилятор проглатывает без проблем. Но при запуске получаем исключение bad_alloc. Ура! Программа грохнулась!
вторник, 2 апреля 2019 г.
std::set - как с ним работать?
Множество обладает свойством уникальности элементов. Как же там хранить какие-то сложные типы данных, как будут сравниваться элементы на равенство? Оказывается, в типе элементов просто нужно перегрузить оператор< . Вот простейший пример:
class mPair
{
int x, y;
public:
mPair(int a, int b)
{
x = a; y = b;
}
bool operator<(const mPair &p) const
{
return x
Оператор < обязательно должен быть оформлен именно таким образом - константный и с константным аргументом.
Кстати, вот статья с крайне подробным разбором std::set.
class mPair
{
int x, y;
public:
mPair(int a, int b)
{
x = a; y = b;
}
bool operator<(const mPair &p) const
{
return x
}
};
};
Оператор < обязательно должен быть оформлен именно таким образом - константный и с константным аргументом.
Кстати, вот статья с крайне подробным разбором std::set.
Подписаться на:
Сообщения (Atom)