Продолжаем разбирать кабанчика («Высоконагруженные приложения» Мартина Клепманна).

В главе 3 рассматриваются особенности хранения и извлечения данных, в частности хэш-индексы, LSM и B-tree, а также отличия баз OLTP и OLAP.

Глава довольно насыщенная, поэтому я разбила ее на несколько постов.

Представим самую простую БД: текстовый файлик, в который мы последовательно записываем данные в формате ключ-значение.
Запись работает быстро, поскольку добавление данных в конец файла обычно эффективно.
Чтение же наоборот работает очень медленно -
каждый раз, когда нужно найти ключ, приходится просматривать всю базу от начала до конца, выискивая вхождения ключа.

Для эффективного поиска значения конкретного ключа в БД необходима другая структура данных – индекс.

Индекс — это дополнительная структура, производная от основных данных. Любые индексы обычно замедляют запись, так как индекс тоже приходится обновлять всякий раз при записи данных на диск. Это компромисс: хорошо подобранные индексы ускоряют запросы на чтение, но замедляют запись. Поэтому БД обычно не индексируют по умолчанию все, что можно, а предлагают разработчикам создать индексы вручную, на основе знания типичных для приложения запросов.

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

Каждый раз при обновлении или добавлении в файл новой пары ключ-значение происходит также обновление хеш-таблицы.

Если нужно найти значение, то мы находим в хеш-таблице ключ и переходим в указанное для этого ключа место в файле, откуда и читаем значение.

Хэш-таблицы работают быстро, но главным недостатком хэш-индекса является неэффективность для запросов по диапазону ключей. Например, если мы построили хэш-индекс по дате, то невозможно с легкостью просмотреть все записи между 2024-08-01 и 2024-08-31 — необходимо искать каждый ключ отдельно.

#сисдиз #кабанчик