Wiki

    Основы БД

    Основы БД

    Хранение данных

    Обычно БД хранят данные в файлах файловой системы, причем записывают новые данные только в конец. Это позволяет добиться хорошей производительности для записи, но для чтения придется перебирать полностью весь файл сначала (сложность О(n)).

    Для улучшения производительности чтения, используют индексы

    Типы индексов

    Хэш-индексы

    attachments/Снимок экрана 2023-08-17 в 20.01.24.png
    Для такого индекса в качестве ключа будет значение заданного индекса (например, по значениям одной колонки), а в качестве значения - относительный адрес (байтовое смещение) того, где находятся данные на диске.

    Ограничения:

    • Хэш-таблица должна помещаться в оперативной памяти, иначе сложно добиться хорошей производительности
    • Неэффективные запросы по диапазону (напр., все записи между qwerty0000 и qwerty9999) - необходимое каждый ключ искать отдельно.

    B-деревья

    TODO

    см. Кабанчик, страница 111

    Способы хранения значений в индексах

    По ссылке

    В этом случае в качестве значения в индексе хранится только ссылка на значение. Сами значения при этом хранятся в неупорядоченном файле (heap file).

    Это упрощает содержание нескольких вторичных индексов, так как не нужно перезаписывать значения в каждом, а лишь в heap файле.

    С другой стороны, лишний переход от ссылки к значению может уменьшать производительность.

    Кластеризованный индекс

    (clustered index)

    Проиндексированная строка хранится сразу в индексе. Это повышает скорость чтения, но увеличивает накладные расходы.

    Пример: в MySQL первичный ключ является кластеризованным индексом, а все вторичные ссылаются на первичный ключ, а не на heap файл.

    Охватывающий индекс

    Охватывающий индекс (covering index) или индекс с включенными столбцами (index with included columns) - компромисс между кластеризованным и некластеризованным вариантами. В нем в индекс включаются лишь некоторые столбцы. Таким образом, можно покрыть индексом часть запросов.

    Составные индексы

    В случае, когда в запросе есть условия сразу по нескольким столбцам, одномерного индекса будет недостаточно. В этот случае используют составные (многомерные) индексы.

    Чаще всего используется сцепленный индекс (concatenated index) - значения колонок просто присоединяются друг к другу (в порядке заданном индексом).