День 2496. #SystemDesign101
8 Структур Данных, Использующихся в БД
Данные могут быть индексированы в памяти или на диске. Аналогично, форматы данных различаются, например, числа, строки, географические координаты и т.д. Система может быть ориентирована на запись или чтение. Все эти факторы влияют на выбор формата индекса базы данных.

Ниже перечислены некоторые из наиболее популярных структур, используемых для индексации данных.

1. Skiplist
Вероятностная структура данных, позволяющая в среднем за O(log(n)) времени выполнять операции добавления, удаления и поиска элементов. Распространённый тип индекса в памяти. Используется в Redis.

2. Хэш-индекс
Структура данных, используемая для быстрого поиска точных совпадений в БД, основанная на хэш-таблицах. Работает с помощью хэш-функции, которая преобразует значение ключа в хэш-код (число), а затем используется для определения "бакета" (корзины), где хранится ссылка на нужную запись.

3. SS-таблица
Формат хранения данных в виде неизменяемого файла на диске, содержащего отсортированные по ключам пары "ключ-значение". Данные из временной памяти (Memtable) сбрасываются на диск в виде SS-таблицы, что делает их постоянными и отсортированными для быстрого доступа.

4. LSM-дерево
Skiplist + SSTable. Cтруктура данных, используемая в БД для эффективного хранения и обработки большого количества записей, особенно при частых вставках и удалениях. Новые данные помещаются в отсортированный буфер в оперативной памяти (Memtable), затем периодически сбрасываются на диск в виде SS-таблиц, которые затем объединяются в фоновом режиме.

5. B-дерево
Сбалансированная древовидная структура данных, которая оптимизирована для работы с большими объёмами информации, хранящейся на диске или во внешней памяти. Каждый узел B-дерева может содержать множество ключей и ссылок на множество потомков, что позволяет уменьшить высоту дерева и, как следствие, сократить количество операций чтения-записи, что критически важно для БД и файловых систем.

6. Инвертированный индекс
Структура данных, которая сопоставляет слова с документами, в которых они встречаются. Является ключевым элементом поисковых систем, так как позволяет быстро находить документы по заданному слову или фразе, перебирая списки документов, а не все документы целиком. Используется в Lucene.

7. Суффиксное дерево
Cжатое дерево, представляющее все суффиксы заданной строки. Позволяет быстро решать задачи, связанные с поиском подстрок, такие как поиск вхождений, поиск самых длинных общих подстрок и т.п.

8. R-дерево
Древовидная структура данных для индексации многомерной, в основном пространственной, информации, такой как географические координаты, прямоугольники или многоугольники. Позволяет эффективно выполнять запросы к таким данным, разбивая пространство на перекрывающиеся области с помощью ограничивающих прямоугольников, и организует объекты в узлах дерева для быстрой фильтрации и поиска.

Источник: https://blog.bytebytego.com