Структуры данных для высоконагруженных приложений: компромиссы и рекомендации
по проектированию

Теперь мы представим параметры пространства проектирования структур данных. Выбор значений этих параметров является фундаментальным проектным решением о том, как хранятся данные типа ключ-значение и как к ним осуществляется доступ. Мы представляем восемь параметров, которые вместе описывают как хорошо известные современные конструкции структур данных, так и ещё не определённые проекты, которые могут быть охарактеризованы в рамках этого пространства проектирования. Вот эти восемь параметров:

Модель затрат: количественная оценка влияния проектирования. В оставшейся части этой главы мы представляем возможные решения для каждого параметра и как они влияют на проектирование с точки зрения производительности PyRUMID.

Для количественной оценки затрат PyRUMID мы используем модель затрат с параметрами, показанными в Таблице 3.1. Это модель ввода-вывода, которая учитывает количество перемещённых страниц диска. Как обсуждалось в предыдущей главе, мы фокусируемся на перемещении данных, так как это основной фактор, влияющий на конечную производительность для приложений систем данных, где вычисления незначительны (например, простые сравнения).

Таблица 3.1: Параметры, охватывающие различные параметры набора данных и организацию данных, которые влияют на затраты доступа к ключам в конкретной структуре данных.

Первое решение при выборе метода доступа — это способ организации данных на страницах или в разделах, или глобальная организация данных (global data organization). Ниже мы представим основные варианты глобальной организации данных и сопроводим каждый из них простым примером для наглядности. Далее мы различаем организации на уровне ключей и на уровне разделов. Организации на уровне ключей определяют, как организованы все ключи в структуре данных (например, отсортированы, хешированы или неупорядочены), а организации на уровне разделов определяют организацию вложенным образом: во-первых, как организовать ключи между разделами, а во-вторых, как организовать ключи внутри раздела (подробнее рассматривается в разделе 3.4).

Условные обозначения: В каждом примере ниже страницы данных разделены символом «;», разделы указаны с использованием «(…)», а весь набор данных заключён в «[ … ]». В отсутствие «(…)» разделов нет. Обратите внимание, что хотя раздел обычно состоит из нескольких страниц, возможно также наличие нескольких разделов внутри одной страницы или одного раздела на страницу.

Отсутствие организации. Пары ключ-значение хранятся на страницах без какой-либо структуры или порядка. В результате любая конкретная пара ключ-значение может появиться на любой странице.
Пример (отображение ключей только на страницах):
[242 2000 1002; 200 49 2304; 25 230 1500]

Отсортированные. Пары ключ-значение сортируются на основе их ключей (обратите внимание, что мы представляем только ключи, но не связанные с ними значения).
Пример (отображение ключей только на страницах):
[25 49 200; 230 242 1002; 1500 2000 2304]

Хеширование. Пары ключ-значение хранятся на основе хэша ключа в хэш-таблице.
Пример (использование в качестве хэш-функции h (x) = x mod 9), хэш-значение в {-}: [{0}: 2304, {1}: 200, {2}: 2000; {3}: 1002, {4}: 49, {5}: 230; {6}: 1500, {7}: 25, {8}: 242].

Логирование. Пары ключ-значение физически хранятся в соответствии с порядком их поступления, образуя журнал.
Пример:
[230 2000 1002; 200 49 1500; 25 242 2304]
На рисунке 3.1 представлены варианты организации данных на уровне ключей с помощью визуального представления, которое мы используем в оставшейся части книги для описания конструкций структур данных.

Разбиение диапазона. Есть P непересекающихся разделов. Каждая пара ключ-значение (k, v) принадлежит единственному разделу, диапазон ключей которого содержит k. Например, если существует три раздела с диапазонами ключей [1, 220), [220, 1200) и [1200, 3000], то коллекция нашего примера может быть разбита следующим образом. В этом примере каждый раздел занимает ровно одну страницу. Далее отметим, что внутри каждого раздела ключи не обязательно должны быть организованы каким-либо определённым образом.
Пример:
[(49 25 200); (1002 230 242); (2000 2304 1500)]

Поразрядное разбиение. Префикс битового представления ключа k пары ключ-значение (k, v) используется для сопоставления (k, v) с определённым разделом. Например, мы можем использовать первые два бита 12-битного двоичного представления ключей в нашем примере набора данных: 25 = 0b000000011001, 49 = 0b000000110001, 200 = 0b000011001000, 230 = 0b000011100110, 242 = 0b000011110010, 1002 = 0b001111101020, 1500 = 0b010111011100, 2000 = 0b011111010000, а 2304 = 0b1001000000.
В результате получится следующее (неравномерное, поскольку большинство ключей маленькие) разбиение:
[ (0b00: 49 25 242; 1002 200 230); (0b01: 2000 1500); (0b10: 2304) ]

Хеш-разбиение. Каждая пара ключ-значение (k, v) попадает в раздел h (k), основанный на хэш-функции h (-). Например, если для простоты изложения использовать простую хэш-функцию h (k) = k mod 3, то коллекция данных в нашем примере будет разбита следующим образом.
Пример, хэш-значение в {⋅}:
[ ({0}: 1002 1500 2304); ({1}: 49 25); ({2}: 230 2000 200 242) ]

Частным случаем хеширования является хеширование с сохранением порядка, которое создаёт непересекающиеся разделы с возрастающими диапазонами значений (Fox и др., 1991; Hutflesz и др., 1988; Robinson, 1986; Sabek и др., 2022).

Разделённое логирование. В качестве альтернативы чистому логированию, разделённое логирование разбивает пары ключ-значение на отдельные временные интервалы, называемые эпохами, где i-я эпоха обозначается как ei. Один и тот же ключ может присутствовать в нескольких эпохах, что приводит к увеличению памяти.
Пример:
[ (e₁: 230 2000 1500; 200); (e₂: 49 1500 25); (e₃: 242 200 2304) ]
На рисунке 3.2 представлены варианты организации данных на уровне разделов. Обратите внимание, что после выбора глобальной организации данных на основе разбиения различные разделы могут иметь различные локальные организации данных, о чем мы поговорим в разделе 3.4.

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

При полном сканировании доступ получают все NB страниц независимо от организации данных, как показано на рисунке 3.3.

Применяется для: всех организаций данных для запросов по точкам или диапазонам.

Производительность точечных и диапазонных запросов. Производительность полного сканирования зависит только от размерности данных и селективности запроса, которые вместе влияют на накладные расходы на оценку предикатов и запись результатов (Kester и др., 2017). С точки зрения затрат на ввод-вывод, при полном сканировании всегда необходимо прочитать O (NB) страниц данных, чтобы найти требуемую пару ключ-значение. Как правило, полное сканирование следует использовать, если (1) поиск/обновление/удаление не имеет информации об организации данных, (2) данные хранятся без какой-либо организации, (3) данные хранятся на основе логирования, но ключ не является монотонным по времени (последовательным), или (4) запрос вернёт большую часть первоначального набора данных.

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

Бинарный поиск использует порядок в данных, чтобы избежать обращения ко всем страницам. В частности, для точечных запросов двоичному поиску требуется доступ только к логарифмическому (по основанию 2) количеству страниц, как показано на рисунке 3.4. Например, если имеется миллион страниц, то двоичный поиск прочитает только 20 страниц.

Применимо к: отсортированным, разбитым на диапазоны, сохраняющим порядок хэшам и организациям с поразрядными разбиениями, для точечных и диапазонных запросов.

Производительность точечных запросов. Бинарный поиск находит нужное значение в отсортированной коллекции за O (⌈log₂(NB)⌉) обращений. Если данные разбиты на P разделов, то поиск должен сначала найти нужный раздел, а затем, в худшем случае, перебрать все страницы в этом разделе, что требует O (⌈log₂ (P)⌉+⌈N_B/P⌉) обращений.

Производительность запросов с диапазоном. Если запрос является диапазонным, то за двоичным поиском первого ключа последуют последовательные обращения к последующим страницам. Стоимость запроса с диапазоном включает компонент, линейно зависящий от доли извлекаемых данных (s%). В случае сортированной организации данных количество совпадающих страниц составляет ⌈s%⋅N_B⌉. С учётом поиска первого ключа стоимость запроса диапазона при отсортированной организации данных составляет O (⌈log₂(N_B)⌉+⌈s%⋅N_B⌉). В случае разбиения диапазона запрос на диапазон будет читать k=⌈s%⋅P⌉ разделов. Таким образом, стоимость запроса диапазона (при отсутствии порядка внутри разделов) составляет O (⌈log₂(P)⌉+k⋅⌈N_B/P⌉) страниц.

Оптимизации. В дополнение к бинарному поиску отсортированную коллекцию можно искать с помощью m-нарного поиска с m группами, что приводит к O (log_m(N)) стоимости поиска (Schlegel и др., 2009). Основная идея этого алгоритма заключается в том, что мы разбиваем пространство поиска (изначально весь массив) на m частей. На первом шаге m-нарный поиск использует SIMD-команды для загрузки и сравнения значений в m позициях массива, чтобы определить, в какой из m частей мы должны искать. Поиск по m позициям выполняется рекурсивно в пределах выбранной части.

Прямая адресация — это стратегия отображения ключа непосредственно на местоположение, возможно, после некоторого преобразования. Например, хэш-структура, основанная на функции H, сопоставляет пару ключ-значение (k, v) с блоком, местоположение которого — H (k). В отличие от этого, деревья двоичного поиска, B-деревья и другие подобные структуры отображают ключи на местоположения на основе серии сравнений.

Применимо к: хэш- и поразрядным разбиениям для точечных и диапазонных запросов.

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

Производительность запросов к диапазонам. Как организации данных на основе разряда, так и хеширование с сохранением порядка поддерживают запросы к диапазонам. В частности, запрос диапазона сначала выполняет поиск начала диапазона квалифицирующих записей за постоянное время, а затем сканирует квалифицирующие записи, что приводит к общим затратам O (1+k⋅⌈N_B/P⌉), где k — количество разделов, прочитанных для диапазона, а N_B/P — среднее количество страниц на раздел.

Поиск, основанный на данных, относится к классу поисковых алгоритмов, которые находятся между поиском сортировки и прямой адресацией. Поиск, основанный на данных, использует имеющиеся знания о распределении данных в качестве подсказки о том, как ориентироваться в данных, как показано на рисунке 3.6.

Применимо к: сортированным, разбитым на диапазоны и радиксным разбитым организациям для точечных и диапазонных запросов.

Производительность. В отличие от двоичного поиска, который отбрасывает примерно половину данных на каждом шаге, поиск, управляемый данными, потенциально может отбрасывать гораздо большую часть данных, используя информацию о распределении данных. Например, если диапазон ключей составляет от 10 до 20 миллионов, ключи распределены близко к равномерному, а ключ равен 18 542 123, то интерполяционный поиск (Perl и др., 1978; Van Sandt и др., 2019; Yao и Yao, 1976) выполнит первый поиск примерно в 85-м процентиле массива. По расчётам, временная сложность составляет в среднем O (log₂(log₂(N_B))) для однородного набора данных (Perl и др., 1978; Yao и Yao, 1976). Другие алгоритмы обобщенного поиска (Kraska и др., 2018) улучшают бинарный поиск в условиях неравномерного распределения данных, сохраняя некоторую характеристику этого распределения.

Экспоненциальный поиск (Bentley и Yao, 1976) начинается с поиска k в позиции bound = L. Если значение v в позиции L меньше k, то поиск выполняется в позиции bound = 2 ⋅ bound. В противном случае начинается бинарный поиск между началом массива и текущей границей. В целом, экспоненциальный поиск имеет временную сложность O (log₂(i_B)), где i_B — индекс страницы, на которой расположен ключ поиска в коллекции данных, что приводит к O (log₂(N_B)) наихудшей производительности. На практике этот алгоритм может быть намного быстрее простого двоичного поиска, когда искомый ключ находится в начале массива, но может быть медленнее (из-за дополнительных затрат на повторное инициирование двоичного поиска), когда искомый ключ находится в конце массива.

В табл. 3.2 приведена стоимость поиска для точечного запроса для каждой из возможных комбинаций организаций данных, с одной стороны (первый столбец), и алгоритмов поиска, с другой стороны (столбцы 2−5). Эти затраты предполагают, что в памяти на момент начала запроса нет данных.

Отметим, что пропущенная запись (отмеченная знаком «-») означает, что комбинация организации данных и алгоритма поиска невыполнима. В табл. 3.3 представлены затраты на поиск для запроса диапазона для каждой возможной комбинации организаций данных и алгоритмов поиска, снова предполагая, что ни один из данных не находится в памяти на момент начала запроса. Обратите внимание, что мы добавили еще одну строку, чтобы сослаться на хэш-разбиение с сохранением порядка.

Таблица 3.2: Затраты на точечные запросы. Все организации поддерживают сканирование, но некоторые организации могут работать гораздо быстрее, используя другие стратегии поиска (бинарный, прямой и основанный на данных). M-нарность меняет основание логарифма с 2 на m (не показано).

Таблица 3.3: Затраты на запросы к диапазонам. Сканирование работает всегда, но другие методы могут работать быстрее, особенно если аппаратное обеспечение поддерживает произвольный доступ к страницам, который так же быстр, как и последовательный доступ к страницам.

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

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

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

Для достижения такого идеального использования памяти требуется политика замены буфера, которая пытается сохранить в памяти наиболее полезные страницы. Широко используемая политика замены наименее недавно использованных страниц (LRU) сохраняет M последних использованных страниц, предполагая, что будущие обращения, скорее всего, будут похожи на недавние. Однако при таком подходе верхние уровни индекса не обязательно остаются в памяти. Например, когда поиск в B⁺-дереве обращается к определённому узлу листа, LRU сохраняет этот узел листа, даже если к нему не будут обращаться еще долгое время. Лучше было бы использовать эту память для внутреннего узла индекса. По этой причине множество политик замены буфера, улучшающих LRU в том смысле, что они стремятся сохранить узлы самого высокого уровня индекса (т. е. те, которые ближе всего к корню), были предложены Чан и др. (1992), Грейфом и Куно (2010b), Джонсоном и Шаша (1994), Мегиддо и Модха (2004), О’Нилом и др. (1993), Сакко (1987) и Стоунбрейкером (1981). Поскольку замена буфера выходит за рамки этой книги, для целей нашей модели затрат мы предполагаем использование идеализированной стратегии, которая сохраняет узлы верхних уровней в быстрой памяти.

В остальной части этого раздела мы связываем алгоритмы поиска, описанные в разделе 3.2, с соответствующими подходами к индексированию.

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

Чтобы ускорить сканирование, можно использовать индекс фильтрации. Фильтрующий индекс — это индекс в памяти, который может указывать, что определенная страница или раздел, находящийся на диске, не имеет отношения к данному запросу и, следовательно, не нужно искать. Мы будем называть часть обобщенных данных «чанком», поскольку гранулярность может быть такой: раздел, страница или группа страниц. В целом цель фильтрующих индексов — уменьшить коэффициент сканирования, то есть долю страниц, которые необходимо просканировать. На рисунке 3.7 показано индексирование с помощью фильтров.

Существует множество таких структур: зонные карты (Moerkotte, 1998), отпечатки столбцов (Sidirourgos и Kersten, 2013), а также фильтры Блума (Bloom, 1970) и их разновидности (Bender и др., 2012; Breslow и Jayasena, 2018; Deeds и др., 2020; Fan и др., 2014; Lang и др., 2019; Pandey и др., 2021). Индекс фильтрации быстро определяет, безопасно ли избегать доступа к разделу базы данных. Например, зонная карта обобщает каждый раздел, используя минимальный и максимальный ключ этого раздела. Эти краткие сводки позволяют поиску, обновлению или удалению полностью пропустить раздел (или потенциально страницу внутри раздела), когда ключ поиска выходит за пределы его диапазона. Аналогично, отпечатки столбцов хранят гистограмму для каждой страницы, и если ключ поиска не лежит в пределах этой гистограммы, то страница может быть пропущена.

В то время как вышеперечисленные методы наиболее полезны при наличии разделения диапазона, фильтры Блума используют хэширование для индексации каждого элемента фрагмента путем задания количества битов битового вектора, как показано на рисунке 3.8. Фильтры Блума могут позволить точечному запросу полностью пропустить доступ к целому разделу, если битовый вектор указывает, что аргумент запроса не может находиться в этом разделе. Обратите внимание, что положительный результат работы фильтра Блума указывает лишь на то, что аргумент запроса может находиться в разделе. Существует некоторая вероятность ложного срабатывания. Эта вероятность настраивается: выделение большего пространства под фильтры Блума за счёт использования большего количества битов для индексации того же количества элементов уменьшит вероятность ложного срабатывания.

Стоимость поиска. Предположим, что размер страницы в байтах равен E⋅B (то есть количество записей на странице x размер записи). Общий размер индекса фильтра Zonemap составляет O (2⋅N_B⋅K), где K — размер ключа. Колоночный импринт, использующий гистограммы размером H байт на страницу, имеет общий размер O (N_B⋅H) байт. Набор фильтров Блума для каждого раздела (или один фильтр Блума для всего набора данных) имеет общий размер O (N_B⋅B⋅BPK/8) байт, где B — количество записей на странице, а BPK — количество битов на ключ для фильтра Блума. В отличие от этого, полный индекс гораздо больше. Рассмотрим, например, резидентный хэш-индекс с коэффициентом загрузки lf (при распространённом значении 90−95%). Общий размер такого хэш-индекса составляет O (N_B⋅B⋅E/lf).

Если предположить, что в буфере памяти достаточно места для хранения этого небольшого количества метаданных, то стоимость точечного запроса с использованием фильтрующих индексов для отсортированных данных может составлять O (1), а для данных, разбитых на разделы, O (N_B/P), в то время как для других организаций данных она зависит от распределения данных по разделам (Moerkotte, 1998; Sidirourgos и Kersten, 2013).

Фильтры и разреженное индексирование. Фильтрационное индексирование отличается от разреженного индексирования (Dong и Hull, 1982; Ramakrishnan и Gehrke, 2002). Рассмотрим точечный запрос по ключу k. Подход с разреженным индексированием укажет максимум на одну страницу данных, которая может содержать k. Напротив, подход с фильтровым индексированием может указать, что несколько страниц могут содержать k. Для разреженного индексирования пространство ключей должно быть разбито: отсортировано для индексов типа B⁺-дерева или разбито на основе функции для хэш-индексов.

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

Как мы уже видели, когда данные отсортированы, бинарный поиск приводит к логарифмической (по основанию 2) стоимости поиска за счёт безопасного отбрасывания половины данных на каждой итерации. Это даёт стоимость O (log₂(N_B)) чтения страниц. Индексы на отсортированных данных эффективно выигрывают в производительности чтения за счёт памяти. В частности, индекс увеличивает основание логарифма с 2 до сотен и более. Это может оказать огромное влияние на производительность.

Например, если N_B составляет миллиард, log2(N_B) = 30, но log₁₀₀₀(N_B) = 3. Чтобы достичь этого, нам нужно разработать древовидные индексы, в которых каждый узел имеет размах около 1000, что означает, что каждый поиск на узле отбрасывает 999/1000 оставшихся возможных узлов. Уровни дерева связаны между собой указателями, которые помогают направить поиск на ограниченное количество обращений к памяти/диску на каждом уровне. Концепция указателей между уровнями называется дробным каскадированием (Chazelle и Guibas, 1985) и является определяющим принципом древовидных индексов. На рисунке 3.9 показан древовидный индекс поиска.

Стоимость поиска: O (logm (N_B)).

Компромиссы: хотя m-нарные деревья при больших значениях m обеспечивают быстрый поиск, такие деревья также необходимо поддерживать, когда отсортированная коллекция ключей изменяется из-за новых данных или обновлений. Чтобы облегчить динамические рабочие нагрузки, как отсортированная коллекция, так и вспомогательные метаданные организуются в логических узлах, часто имеющих некоторое пустое пространство. Результирующее дерево может быть изменено на месте (например, путём вставки новых записей в пустое пространство одного листового узла) без необходимости перемещения больших объёмов данных. Однако за пустое пространство приходится платить. Узлы внутреннего дерева с пустым пространством не только занимают больше общего дискового пространства, но и имеют меньшее разветвление на выходе, чем полные узлы. В некоторых случаях меньшее разветвление на выходе означает увеличение количества уровней дерева.

Вместо сканирования или итеративного поиска альтернативный подход заключается в использовании двоичного представления ключа k для непосредственного нахождения места, где k и связанное с ним значение физически хранятся, с помощью хэширования или поиск радикса. Хеширование особенно хорошо подходит для сильно перекошенных распределений, поскольку оно присваивает почти одинаковые ключи разным разделам. Например, простая хэш-функция h (k)=k mod 101 хэширует 100 последовательных ключей в 100 различных разделов. На рисунке 3.10 показана визуализация хэш-индексации.

Стоимость поиска: В среднем O (N_B/P). Обратите внимание, что если разделы имеют разные параметры, то наибольшая стоимость зависит от размера самого большого раздела.

Другой подход, который можно рассматривать как гибрид классических деревьев поиска и прямой адресации, — это дерево поиска со сжатыми внутренними узлами, или радиксное дерево (radix tree). Хотя первые применения радиксных деревьев были связаны с хранением строк, сейчас радиксные деревья часто используются для хранения произвольных пар ключ-значение, используя при поиске побитовое (радиксное) представление ключа. Радиксные деревья (также называемые префиксными или триксными) поддерживают поиск, ассоциируя части ключа с каждым ребром дерева, как показано на рисунке 3.11 (Morrison, 1968). Общий префикс всех ключевых строк хранится в корневом узле. Перемещение по радиксному дереву подразумевает сопоставление битов с каждым ребром. В контексте управления данными проект радиксных деревьев был доработан с учетом аппаратных соображений (Mao и др., 2012) и свойств данных (Leis и др., 2013).

Радиксные деревья имеют и другие применения. Например, Weiner (1973) предложил суффиксные деревья. Суффиксные деревья принимают на вход набор ключей строк и формирует радиксное дерево всех суффиксов этих строк. Эта структура данных обеспечивает эффективный поиск подстрок, а также поиск последовательных подстрок, наиболее длинных повторяющихся подстрок, наиболее длинных общих подстрок и другие подобные поиски в индексированной коллекции строк.

Классическое дерево поиска (например, B⁺-дерево) имеет внутренние узлы, которые используют значения из области поиска в качестве «разделителей» для создания внутренней иерархии узлов. Поскольку все эти значения происходят из одного и того же домена, каждый узел должен хранить только различающую информацию. Теперь предположим, что у нас есть двоичное представление домена (или радикс), которому требуется r битов для представления каждого индексируемого значения.

Если задан ключ, поиск с использованием базового радиксного дерева начинается с корня и разветвляется на каждый бит ключа по очереди слева направо. Для повышения эффективности использования пространства и уменьшения случайного доступа при обходе дерева узлы, которые имеют допустимые значения только в одном дочернем дереве, могут быть объединены с ним. Дополнительной экономии места можно добиться, свернув все поддерево в один узел. Простой пример приведен на рисунке 3.11. Радиксные деревья можно сжимать двумя способами. Первый — это слияние узлов, при котором двоичные узлы объединяются со своими родительскими узлами — показано в левой нижней части рисунка 3.11(B). Слияние узлов может применяться рекурсивно на нескольких уровнях. Второй способ — удаление поддерева, когда все поддерево может быть удалено, если в его листовых узлах нет ключей, показано в крайней правой части рисунка 3.11(B), где поддерево для ключей с префиксом 10 полностью удалено, поскольку не существует ни 100, ни 101. Сжатие с удалением поддеревьев особенно эффективно для перекошенных данных. Когда данные не перекошены, все или большинство поддеревьев будут иметь ключ в одном из своих листовых узлов.

Практичный вариант — использовать 4 или 8 бит радикса в одном узле, который будет иметь 16 или 256 дочерних узлов (Leis и др., 2013), соответственно. Такой узел радиксного дерева помещается в несколько строк кэша и сохраняет высокую локальность, обеспечивая эффективную навигацию в ключевой области. Радиксные деревья и их оптимизированные по пространству варианты эффективно поддерживают как точечные, так и запросы к диапазонам.

Стоимость поиска: O ([log₂S (u)])=O[log₂(u)/S], где u — максимальное значение домена, поэтому [log₂(u)] — это количество битов, необходимых для этого максимального значения, а S — количество битов радикса, используемых в каждом узле. Например, для 32-битного домена, если мы используем радиксное дерево с узлами, хранящими 8 бит радикса, высота дерева будет равна log2232/8 = 32/8 = 4. Обратите внимание, что стоимость запроса на поиск точки в радиксном дереве зависит не от размера данных, а от максимально возможного значения домена. Оптимизация, которая позволит стоимости поиска использовать распределение данных, заключается в динамической настройке S, чтобы она была разной в разных частях домена (Leis и др., 2013), и в разрушении путей деревьев, которые ведут только к одному узлу листа, как показано на рисунке 3.11.

Все представленные до сих пор индексы, которые ориентированы как на точечные, так и на диапазонные запросы, поддерживают отсортированную, основанную на диапазонах или радиксную версию данных и создают метаданные для навигации. Эти метаданные основаны на организации данных. Операции над структурой данных могут использовать эту метаинформацию для прямого доступа к целевым записям данных, не читая остальные данные. С другой стороны, эта навигационная метаинформация может требовать значительного объёма памяти, так как она включает явное поддержание порядка ключей.

Альтернативным вариантом проектирования индекса является сохранение порядка ключей в виде модели, а не явных ключей. Основная идея алгоритмов поиска, основанных на модели, заключается в вычислении ожидаемой позиции записи данных с помощью знания распределения ключей. Например, оригинальная концепция обучаемых индексов (Kraska и др., 2018) предлагает сортировать все записи данных и изучать их распределение путем построения модели машинного обучения. Затем при поиске по структуре данных используется модель для предсказания ожидаемого местоположения записи данных с учетом её ключа. Учитывая это предсказание, запрос может искать точный слот записи данных на странице данных. Однако до тех пор, пока модель указывает на нужную страницу данных, общая стоимость ввода-вывода всё ещё сводится к чтению одной страницы (например, для точечного запроса). Это показано на рисунке 3.12.

Один из подходов к созданию обучаемого индекса заключается в построении единой модели для представления всех данных. Например, модель для плотного равномерного распределения может сказать, что ключ k будет находиться на странице 1000+k/100. Это означает, что весь индекс заменяется одной моделью. Однако это крайний случай, и основная идея может быть доработана путём разбиения пространства на части, как в классическом древовидном индексе, а затем принятия дальнейших проектных решений о том, как ориентироваться в дополнительной структуре.

Создание последнего уровня индексации обучаемого дерева. Современные конструкции обучаемых индексов принимают решение сначала разбить отсортированные данные на множество непрерывных частей, называемых сегментами, каждый из которых содержит одну или несколько страниц. Внутри каждого сегмента может быть создана отдельная модель, которая стремится достичь желаемой границы ошибки. Это необходимо для хорошего предсказания модели и, следовательно, для производительности ввода-вывода. Один из способов мыслить о сегментах и моделях, представляющих эти сегменты, заключается в том, что они представляют собой предпоследний уровень классического дерева (то есть последний уровень внутренних узлов B⁺-дерева).

Напомним, что в классическом многоствольном дереве каждый внутренний узел с коэффициентом разветвления F, имеет F указателей, по одному на целевую страницу, и F — 1 разделителей ключей.

В отличие от этого, обучаемый индексный узел, использующий линейную модель, аппроксимирует связь между F — 1 значениями и F указателями, которые необходимо отслеживать при поиске, с помощью линейной аппроксимации вида pos = value ⋅ α + β. Следовательно, вместо того чтобы хранить F — 1 ключей и F указателей, необходимо хранить только два коэффициента α и β, начальный ключ сегмента, а также один указатель/смещение на сегмент.

В отличие от этого, листовые узлы обучаемого индекса занимают столько же места, сколько и листья B⁺-дерева. Таким образом, главное преимущество заключается в том, что внутренние узлы занимают гораздо меньше места, как показано на рисунке 3.13.

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

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

Создание остальных уровней индексации. После создания сегментов подходы к формированию остальной навигационной структуры различаются. Например, Ferragina и Vinciguerra (2020) предлагают индекс PGM, который рекурсивно создает дополнительные модели для индексации самих сегментов, таким образом, создавая полное обучаемое дерево моделей. С другой стороны, Galakatos и др. (2019) предлагают FITing-Tree, который использует классическое B⁺-дерево для индексации каждого сегмента. Последний подход создает гибридное дерево, сочетающее классические узлы и модели для последнего уровня, то есть для наиболее потребляющего пространство уровня индекса и того, который действительно «указывает» на данные.

Компромиссы производительности. Обучаемые индексы уменьшают размер индекса за счёт потенциальных ошибок индексирования, когда поиск обращается к неправильному дочернему узлу и поэтому должен выполнять дополнительные чтения для исправления таких ошибок. Кроме того, обучаемые индексы могут требовать значительных усилий по поддержке при обновлениях. Если обновление существенно изменяет распределение ключей, то структуре данных необходимо переобучить свои модели, что может быть временно затратным (Ding et al., 2020b). Если обновления избегают переобучения моделей, то будущие поиски могут быть очень медленными, поскольку оценка местоположения записей данных может быть высоко неточной.

Стоимость поиска: Идеальная стоимость обучаемого индекса — O (1), поскольку он напрямую вычисляет, к какой странице нужно обратиться, используя очень маленькие метаданные, которые легко помещаются в память, а затем нужно прочитать только одну страницу. Однако эта идеальная стоимость может быть недостижима, если базовое распределение ключей имеет несколько поддиапазонов ключей с дубликатами или с различными распределениями, в этом случае регрессионная модель будет неточной и будут возникать позиционные ошибки, требующие обращения ко многим страницам листа. Даже если распределение ключей является дружественным, его изучение может потребовать значительного времени.

В целом, необходимо учитывать три различных компонента затрат: затраты на доступ к индексу до завершения обучения, затраты на его завершение и затраты на переобучение моделей после внесения изменений. Эмпирически стоимость поиска составляет O (1) для точечных запросов и O (k) для запросов на диапазон, когда требуется k страниц, но стоимость обучения не имеет фиксированной верхней границы и зависит от сложности моделей, а также свойств данных и частоты обновлений (Kraska и др., 2018).

Здесь мы приводим стоимость точечных и диапазонных запросов при использовании индексирования для поиска, а также стоимость вставки новых записей в каждой из стратегий индексирования. Мы предполагаем, что у нас есть M страниц доступной памяти. Если M больше размера индекса фильтра (например, когда M>2⋅N^B⋅K для Zonemaps), то индекс фильтра может храниться в памяти и приносить максимальную пользу при поиске. Аналогично, коэффициенты из выученных индексов занимают мало места в памяти, поэтому их можно хранить в памяти. Для B⁺-деревьев и их разновидностей верхние уровни (столько, сколько займет M страниц) будут находиться в памяти при условии идеального алгоритма замены страниц.

Таблица 3.4: Стоимость поиска для точечных запросов при использовании индекса. Каждая строка соответствует одному решению по организации данных («Орг.»), а каждый столбец — решению по индексированию. Обратите внимание, что некоторые комбинации невозможны, то есть конкретный тип индекса не поможет найти ключ при данной организации данных (отмечены знаком «-»).

Таблица 3.5: Стоимость поиска для диапазонных запросов с селективностью s% при использовании индекса. Таблица имеет ту же структуру, что и табл. 3.4.
∗ Заметим, что запрос диапазона с использованием хэш-индекса использует количество записей N и может работать только в случае дискретного домена.
∗∗ Кроме того обратите внимание, что хеширование с сохранением порядка позволяет почти оптимально использовать только последовательное чтение соответствующих страниц данных.

В табл. 3.4 приведена стоимость точечного запроса для каждой возможной методики индексирования с учетом организации данных. В табл. 3.5 приведены затраты на запрос диапазона с селективностью s%. Если в запросе используется дерево поиска или радиксное дерево, стоимость вычисляется путем добавления соответствующей стоимости точечного запроса из табл. 3.4. Далее отметим, что стоимость хэш-индекса зависит от количества записей N, а не от количества страниц NB, и применима только в тех случаях, когда область дискретна и мы можем сопоставить запрос диапазона с несколькими точечными запросами. Такой подход к отображению быстро становится неэффективным даже для очень выборочных запросов. С другой стороны, в случае использования хеширования, сохраняющего порядок, запрос диапазона будет иметь близкую к оптимальной стоимость.

Наконец, в случае с обучаемыми индексами мы определили несколько комбинаций, которые возможны, но в настоящее время являются предметом активных исследований, и мы помечаем их как «(открытые)».

Таблица 3.6: Стоимость вставки индекса

И наконец, в табл. 3.6 мы рассмотрим стоимость вставки в основных классах индексных структур. В недавней литературе встречаются некоторые подходы к обновлению выученных индексов (Ding и др., 2020b), однако вопрос о том, как выполнить эффективное обновление, на момент написания этой статьи остается открытым.

После принятия решения о глобальной организации данных, методах поиска и использовании индексации для ускорения поиска нужной страницы в разделах 3.1, 3.2 и 3.3 мы должны принять решение о локальной организации данных, то есть о том, как организовать каждый раздел. В данной структуре данных разные разделы могут быть организованы по-разному. Ниже мы представим пять локальных организаций данных, которые визуализированы на рисунке 3.15.

В дополнение к общей цели создания метаданных, помогающих быстро находить искомые элементы данных, локальный поиск ставит новые задачи. Одна из них заключается в том, что локальная организация данных должна помещаться в строки кэша, чтобы исключить обращение к оперативной памяти. На некоторых аппаратных средствах локальная организация предназначена для лучшего размещения SIMD-инструкций. Кроме того, операции в локальных организациях часто пытаются избежать выделения новой памяти при каждой вставке или обновлении.

Логирование. Записи в разделе добавляются в массив в порядке возрастания времени, формируя log.

Хеширование. Раздел использует внутреннюю хэш-структуру для хранения (и определения местоположения) пар ключ-значение в пределах этого раздела.

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

Диапазон. Содержимое раздела хранится в виде диапазона, разделенного по ключу, возможно, с несортированной организацией этих подразделов.

Разделённый. Содержимое разделено. То есть изначально данные логируются, но при выполнении запроса (обычно запроса на диапазон) данные могут быть адаптивно организованы, чтобы стать отсортированными или разделёнными на диапазоны. В главе 5 подробно рассматривается этот метод и его обобщения

Последствия для производительности. Каждая локальная организация данных имеет такие же последствия для производительности на локальном уровне, как и соответствующая глобальная организация данных без индексов на глобальном уровне. Например, двоичный поиск возможен, если локальная организация данных отсортирована. Ключевое отличие заключается в том, что локальные данные часто умещаются в памяти. Кроме того, принятие различных глобальных и локальных решений может привести к появлению гибридных моделей затрат. Например, организация данных может сочетать разбиение на разделы н, а глобальном уровне с хешированием, сортировкой или взломом на локальном уровне.

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

Последовательный поиск. Любая локальная организация данных для содержимого одного раздела или страницы может быть найдена с помощью последовательного поиска, который проверяет все записи типа «ключ-значение».

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

Сортированный поиск. Если данные в разделе отсортированы, можно использовать алгоритм поиска с сортировкой, например двоичный поиск, m-ариевый поиск или какой-либо алгоритм поиска, управляемый данными. Соображения аналогичны тем, что описаны в разделе 3.2 для сортированной глобальной организации.

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

Для каждого организованного сбора данных входящая модификация (то есть обновление, вставка или удаление) ключа k будет либо:

Выполните модификацию на месте: при вставке поместите пару (k, v) куда-нибудь в структуру, если k нигде не присутствует; при обновлении замените значение, связанное с k, новым значением; при удалении удалите k и связанное с ним значение. В результате сохраняется инвариант единственной копии, согласно которому в структуре всегда есть не более одного экземпляра k. Этот инвариант выполняется для исторически знакомых структур данных, таких как хэш-структуры и B-деревья.

Выполните модификацию вне места: каждая модификация будет проявляться как добавление пары (k, v) в некоторое ранее пустое место. Таким образом, ключ k может встречаться в структуре много раз, что приводит к многокопийной организации данных. Поиск, следующий за модификация k должна определить, какая пара ключ-значение для k была самой последней, и вернуть связанное с ней значение (которое при удалении k будет «надгробием», указывающим на отсутствие значения, связанного с k). За модификациями вне места обычно следует периодическое удаление дубликатов и недействительных элементов, чтобы уменьшить усиление чтения и занимаемого пространства.

Модификация на месте обычно соответствует той глобальной и локальной организации данных, которая существовала до модификации. Например, если у нас есть отсортированная коллекция и мы вставляем новую пару ключ-значение (k, v), она должна быть вставлена в позицию, продиктованную рангом k в порядке сортировки, как показано на рисунке 3.16. Если организация данных предусматривает разбиение на диапазоны, то новый элемент должен быть физически помещен в соответствующий раздел. Модификация на месте — это политика, используемая в базовых структурах данных, включая учебные B⁺-деревья, хэш-индексы, сортированные связные списки и другие. Модификации на месте в таких структурах данных отличаются высокой производительностью чтения, но могут нести бремя реорганизации для модификаций.

Влияние на затраты PyRUMID. Стоимость модификации на месте равна стоимости точечного поиска пары ключ-значение для модификации и как минимум еще одного обращения к записи, чтобы убедиться, что обновленная пара ключ-значение находится на диске. Стоимость этого подхода представлена в табл. 3.6.

Нештатная модификация ключа k позволяет избежать вмешательства в текущую организацию данных. Вместо этого модификация может храниться отдельно от любых других экземпляров k в структуре данных. Следуя парадигме деревьев Log-Structured Merge (LSM), первоначально предложенных O’Neil и др. (1996) и рассмотренных Luo и Carey (2020), модификации вне места (а) регистрируются как часть контейнера в памяти, поэтому для модификаций не требуется обращений к диску и (б) они не влияют на организацию или стратегию доступа к существующим данным, как показано на рисунке 3.17. В LSM-дереве любая новая или измененная запись просто добавляется в буфер, находящийся в памяти. Когда буфер становится полным, она вытесняется в контейнер на диске в виде набора пар ключ-значение. В результате любой запрос на чтение может потребовать поиска в нескольких контейнерах данных для получения окончательного ответа, как показано на рисунке 3.18. Пространственные модификации вне места допускают дублирование, поскольку для данного ключа k может существовать несколько пар ключ-значение.
Консолидация. Накопленные модификации могут создавать недействительные записи данных либо в результате удаления, либо в результате обновления. Эти недействительные копии, в свою очередь, увеличивают пространственную амплификацию структуры данных и амплификацию чтения, что приводит к ухудшению производительности чтения, поскольку необходимо просеять больше данных, чтобы найти нужную запись. Для решения этой проблемы за модификациями вне места обычно следуют периодические консолидации, объединяющие существующие данные. Например, в LSM-дереве различные отсортированные прогоны объединяются в один отсортированный прогон. Во время этой фазы консолидации, которую также называют уплотнением, сборкой мусора или просто объединение — дубликаты и недействительные записи отбрасываются. Обратите внимание, что консолидация обязательно перезаписывает ранее добавленные данные, а значит, увеличивает усиление записи, но при этом уменьшает количество отсортированных прогонов, к которым нужно обращаться, что повышает производительность чтения. Это классическое проявление трехстороннего компромисса между стоимостью чтения, обновления и хранения, описанного в разделе 2.3.

Влияние на стоимость PyRUMID. Модификации вне места агрессивно минимизируют стоимость модификации за счёт увеличения стоимости чтения и использования пространства. Когда модификация вне места добавляется к буферу в основной памяти, она требует нулевого обращения к диску. Однако поиск должен найти соответствующий раздел или страницу и может выполнить локальную реорганизацию. Практические проекты систем, использующих модификации вне места, такие как хранилища ключевых значений на основе LSM, уменьшают занимаемое пространство и усиление чтения за счёт слияния отсортированных прогонов для формирования более длинных отсортированных прогонов, которые имеют меньше или вообще не имеют дубликатов и более удобны для поиска. Базовая конструкция LSM-дерева показана на рисунке 3.19. Более подробно структура данных LSM-дерева рассматривается в разделе 4.8.

Практическое сравнение «на месте» и «вне места». По сравнению с подходом на месте, модификации вне места значительно уменьшают усиление записи при получении данных. Например, Сирс и Рамакришнан (Sears и Ramakrishnan, 2012) отмечают, что у B⁺-деревьев усиление записи может достигать 1000, в то время как модификации вне места в хранилищах ключевых значений на основе LSM имеют значительно меньшее усиление записи обычно от 10 до 40, что приводит к повышению эффективности захвата на 25x-100x (Sarkar и др., 2021; Dong и др., 2017). В более ранней работе Сирс и Рамакришнан (Sears и Ramakrishnan, 2012) показали, что для рабочей нагрузки, связанной только с занесением данных на (тогда) современный SSD, bLSM, их система на базе LSM, достигла 32 тыс. оп/с по сравнению с 2 тыс. оп/с для базовой InnoDB, которая является механизмом хранения MySQL на основе B⁺-деревьев. Несмотря на постоянное развитие технологии, уменьшенное усиление записи LSM-деревьев и их разновидностей по сравнению с структурами данных на месте дает LSM-структурам преимущество в тяжелых для вставки рабочих нагрузках.

Разновидностью модификаций вне места является концепция дифференциальных модификаций вне места. При обновлении значения, связанного с ключом k, дифференциальные модификации вне места хранят ключ k и разницу между старым значением, связанным с k, а не хранят все новое значение (Severance и Lohman, 1976), что потенциально экономит место. Это позволяет экономить место при обновлении, но может привести к увеличению затрат при запросах на чтение, поскольку может потребоваться восстановить значение, связанное с k, из нескольких пар ключ-значение. Такой дифференциальный подход наиболее полезен, когда значения велики (например, файлы изображений или видео), а модификации могут быть выражены лаконично. Однако дифференциальный подход не будет полезен для значений, состоящих из целых чисел, чисел с плавающей запятой или строк скромного размера.

Влияние на стоимость PyRUMID. Дифференциальные модификации вне места уменьшают занимаемое пространство за счёт более дорогого поиска, поскольку они требуют восстановления текущего логического значения из базового и, возможно, нескольких дифференциальных значений.

Помимо использования основной памяти для индексирования метаданных, основная память может использоваться для буферизации запросов на чтение и запись. Цель состоит в том, чтобы применить несколько запросов (обычно называемых «пакетными») за один раз.

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

Примеры. В системах аналитических данных используются совместные сканирования (также известные как кооперативные сканирования) (Arumugam и др., 2010; Candea и др., 2009; Giannikis и др., 2012; Harizopoulos и Ailamaki, 2003; Harizopoulos и др., 2005; Johnson и др., 2007; Mehta и др., 1993; Psaroudakis и др., 2013; Qiao и др., 2008; Unterbrunner и др., 2009; Zukowski и др., 2007), которые объединяют несколько длинных запросов, используя общие доступы к данным для достижения одновременного выполнения длинных запросов с низкой загрузкой процессора и диска. Одного обращения к набору данных достаточно для ответа на все запросы партии при условии, что имеется достаточно буферного пространства для запросов на чтение и бухгалтерия для отслеживания того, какие элементы соответствуют тому или иному запросу.

Влияние на затраты PyRUMID. Буферизация чтений увеличивает пропускную способность чтения за счёт увеличения времени отклика и дополнительного места для хранения пакетных чтений.

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

В качестве примеров можно привести взломы (Idreos и др., 2007a), деревья буферных хранилищ (Brodal и Fagerberg, 2003) и фрактальные деревья (Kuszmaul, 2014). Другой вариант буферизации модификаций создает дополнительные метаданные в основной памяти, чтобы указать, где новая модификация (модификации) в конечном итоге будет находиться в базовой структуре данных (Héman и др., 2010). Это приводит к высокой производительности запросов как к базовым данным, так и к ожидающим модификациям, при условии, что все ожидающие модификации помещаются в памяти.

Влияние на затраты PyRUMID. Каждая модификация ассоциируется с разделом, к которому она относится, но помещается в буфер. Позже раздел реорганизуется с учетом модификаций в буфере. Это снижает общие затраты на реорганизацию, но может увеличить время поиска, поскольку буфер может быть просканирован при чтении, чтобы определить последнее значение, связанное с ключом поиска.

Кроме того, буферизованные модификации могут храниться локально на основе каждого раздела, а не в глобальном буфере для всей структуры данных. В качестве примера можно привести Bϵ-дерево (Bender и др., 2015), которое напоминает B⁺-дерево, но при этом использует буфер для каждого внутреннего узла, чтобы накапливать входящие модификации перед их передачей на следующий уровень дерева (и, в конечном итоге, в соответствующий листовой узел). Мы подробно обсудим B⁺-деревья в разделе 4.3.

Локальная буферизация позволяет легко обрабатывать каждый раздел по отдельности. Выбор раздела для обработки может зависеть от того, сколько модификаций было буферизовано для каждого раздела (насколько «горяч» каждый раздел д л я записи) и от поискового трафика к разделу.
Влияние на затраты PyRUMID. Как и глобальная буферизация, локальная буферизация использует дополнительное пространство для применения модификаций для каждого раздела. Обработка пакета модификаций для одного раздела, как правило, более эффективна при использовании локальной буферизации, чем при использовании глобальной буферизации.

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

Влияние на затраты PyRUMID. Закрепление в кэше — это явный запрос на сохранение популярных или полезных страниц в кэше. Это гарантирует более низкую задержку для кадров с прикрепленными страницами, но оставляет меньше кэш-памяти доступной для остальных страниц.

Независимо от проекта индекса, мы должны решить, как физически расположить ключи и значения. Это называется представлением пары ключ-значения. Ниже мы рассмотрим различные варианты представления содержимого.

Разделение ключей и значений. Первое решение — хранить ли ключи и значения физически близко друг к другу. По умолчанию в большинстве структур данных они располагаются рядом. Однако, поскольку значение не используется при поиске, разделение ключа и значения может увеличить скорость поиска (Lu и др., 2016).

Естественный способ индексирования таблицы заключается в том, чтобы связать с каждым ключом целую запись. То есть запись представляет собой значение в паре ключ-значение. Такой подход распространен в хранилищах данных NoSQL и куче файлов. Ключ представления записей называется альтернативным-1 представлением данных в (Ramakrishnan и Gehrke, 2002).

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

Если метод доступа находится исключительно в памяти или использует перестановку указателей (Wilson, 1991) для преобразования смещений в адреса в памяти (Graefe и др., 2014), содержимое метода доступа представлено индексированным ключом и соответствующим указателем (ями). Представление содержимого в виде ключа-указателя полезно, когда запись, связанная с ключом, не перемещается, а наличие указателя ускоряет доступ к данным.

Если записи хранятся в отдельном файле, то мы можем использовать идентификатор строки, чтобы найти позицию записи, связанной с ключом. Такой подход часто используется, когда базовые данные хранятся в отдельном файле кучи в системе баз данных или когда записи хранятся в отдельном контейнере, например в журнале. Этот подход называется alternative-2 или alternative-3 (Ramakrishnan и Gehrke, 2002) и соответствует классическому проекту системы баз данных для вторичных индексов. Обратите внимание, что идентификаторы записей могут быть логическими (например, первичные ключи) или физическими (например, идентификатор страницы и идентификатор слота). Представление содержимого Key-RowID хорошо подходит для запросов, которым не важно содержимое строки (например, для запросов на подсчёт). Оно также полезно, когда рабочая нагрузка выдает частые обновления, изменяющие размер строки, что привело бы к значительным затратам на реорганизацию, если бы указатели на записи хранились в индексе.

Существенно отличный вариант — связать битовый вектор с каждым отдельным значением ключа. Это относится к случаям, когда существует несколько различных ключевые значения (например, пол, дни недели) и относительно много записей. Набор битовых векторов представляет собой битовую карту (Chan и Ioannidis, 1998).

Например, предположим, что у нас есть три уникальных ключа k1, k2, k3 и в целом пять записей. Каждый ключ будет связан с битовым вектором длиной 5 бит. Теперь считаем, что первая запись равна k1, вторая и четвертая — k2, а третья и пятая — k3. Битвектор для k1 будет равен 10 000, битвектор для k2 — 1 010, а битвектор для k3 — 101, как показано на рисунке 3.20.

Битовые векторы обычно подвергаются сильному сжатию с помощью различных схем кодирования, таких как Byte-aligned Bitmap Compression (Antoshenkov, 1995), Word-Aligned Hybrid (Wu и др., 2006), Position List Word Aligned Hybrid (Deliège и Pedersen, 2010) и других (Chan и Ioannidis, 1999; Colantonio и Di Pietro, 2010). Ключевым преимуществом большинства схем кодирования битовых векторов является то, что данные можно обрабатывать непосредственно на битовых векторах для выполнения ряда операций, включая выборку, проекцию, объединение и сортировку. Битовые векторы могут также использовать эффективные машинные побитовые операции для очень быстрой обработки данных (Ding и др., 2020a).

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

Таблица 3.7: Проектное пространство методов доступа

Теперь мы представляем коллекцию экспертных правил, которые могут помочь проектировщику выбрать или изобрести метод доступа в зависимости от рабочей нагрузки и доступных ресурсов. Мы обнаружили, что наиболее важными являются три фактора: (1) наличие запросов на дальность, (2) важность характеристик модификации и (3) допустимость усиления пространства.
1. Преобладающий диапазон: если запросы с диапазоном преобладают, используйте сортировку, хеширование с сохранением порядка или организацию данных с разбиением на диапазоны/радиксы (раздел 3.1).
2. Только точки: если в рабочей нагрузке присутствуют только точечные запросы, то хэш-партизация часто будет быстрее, чем сортированная или разбитая на диапазоны глобальная организация данных (раздел 3.1), а хэшированная локальная организация данных будет предпочтительнее сортированной.
3. Выборочные запросы: если точечные или диапазонные запросы являются выборочными, то есть обращаются к небольшой части записей, то полезными будут индексирование (как описано в разделе 3.2) и глобальное разбиение данных (раздел 3.3).

• Малая оперативная память: если индекс не помещается целиком в оперативной памяти и используется индексирование, то для частей индекса, находящихся на дисковом носителе, необходимо обеспечить высокий fan-out. Поэтому B⁺-дерево или хэш-индекс предпочтительнее структуры с низким разветвлением на выходе, например двоичного дерева поиска (разделы 3.3.3 и 3.3.4).

4. Время поиска, не зависящее от размера: когда размер данных увеличивается и мы хотим отвязать время поиска от размера данных, мы можем использовать прямую адресацию (раздел 3.2.3) в виде хэш-индексации (раздел 3.3.4), если наша рабочая нагрузка содержит только точечные запросы, или индексацию на основе радикса, когда базовые данные отсортированы и организованы на основе радиксного разбиения (раздел 3.3.5). Радиксные деревья (раздел 3.3.5) особенно полезны, когда индексируемые данные сильно перекошены, поскольку само дерево может занимать меньше места, чем в случае, когда ключи распределены по пространству ключей более равномерно.
5. Частота модификаций: если вставки/удаления происходят часто, то мы различаем умеренный и интенсивный трафик модификаций. В частности, при интенсивном трафике модификаций мы можем захотеть использовать логирование, разделенное логирование или хэширование на глобальном уровне (раздел 3.1). Если трафик модификаций умеренный, то на глобальном уровне может быть больше гибкости (например, может подойти стиль B⁺-дерева), а на локальном уровне может использоваться хэшированная или логированная организация локальных данных (раздел 3.4). Также отметим следующие положения:

• Пакетная обработка может заменить локальное логирование: проект, использующий локальную организацию данных с логированием для поддержки трафика модификаций, может вместо этого использовать высокоорганизованную (например, отсортированную) локальную организацию данных, а затем выполнять пакетную обработку модификаций либо глобально (раздел 3.7.2), либо локально (раздел 3.7.3).
• Перекрывающиеся разделы требуют фильтров: в проекте, использующем разделенное логирование в качестве глобальной организации данных, следует также использовать легкую индексацию фильтров (например, фильтры Блума), чтобы устранить по крайней мере некоторые ненужные обращения к страницам (раздел 3.3.2).

6. Всплески запросов: если возникают всплески запросов на чтение, их объединение в пакет позволяет сократить избыточные обращения к данным. Выгода максимальна, когда запросы группируются вместе на основе локальности ключа, т. е. путем объединения запросов, направленных на один и тот же раздел (или группу разделов). Пакетирование запросов на чтение увеличивает общую пропускную способность, но также потенциально увеличивает время отклика отдельных операций (раздел 3.7), которые должны ждать, пока их пакет будет обработан.
7. Всплески обновлений: если в отсортированных данных происходят всплески обновлений, то для снижения общих затрат на реорганизацию следует использовать пакетную обработку обновлений (раздел 3.7.2).
8. Только сканирование: если запросы представляют собой полное сканирование или запросы с большим диапазоном, то индексирование не требуется (раздел 3.2.1 и раздел 6.1.2). Сканирование больших диапазонов можно оптимизировать с помощью зонных карт, фильтров Блума и других форм индексирования фильтров (раздел 3.3.2).
9. Сканирование с логированием: если запросы представляют собой полное сканирование или запросы с большим диапазоном и основаны на времени вставки, то следует использовать логирование по времени (раздел 3.1). Также следует использовать индексирование фильтров (например, зонные карты в данном случае) (раздел 3.3.2).
10. Локальность против гибкости: решение о хранении ключей-значений ортогонально другим размерностям. Если главной целью является локальность данных, ключи и значения должны храниться вместе. С другой стороны, при построении индекса, обычно вторичного, на уже организованном наборе записей, каждый ключ индекса должен быть сопряжен с указателем на запись или идентификатором строки, а не дублировать записи. Кроме того, если в рабочей нагрузке происходят обновления, которые могут сильно повлиять на размер значений, то ключи и значения следует хранить отдельно, чтобы избежать реорганизации движения данных, связанной с этими обновлениями.

В следующей главе мы обсудим, как использовать эти правила как для выбора между существующими проектами для заданной рабочей нагрузки, так и для предложения новых проектов, если ни один из существующих проектов не удовлетворяет всем требованиям.

В этой главе описаны восемь основных параметров проектирования методов доступа. Первые четыре параметра касаются структуры как на глобальном, так и на локальном уровнях. Следующие три параметра касаются выбора способов реализации операций. Последний параметр описывает различные варианты организации структуры ключ-значение. Глава завершается представлением экспертных правил, которые сопоставляют нагрузки с выбором проектных решений.

Моделирование: Прочтение Brodal и Fagerberg (2003), Hellerstein и др. (2002), Yi (2009) и Yi (2012) даёт более глубокое представление детального моделирования различных операций в структурах данных.

Проект, основанный на трансформации: следующая серия работ основана на декомпозиции рабочих нагрузок и рассмотрении каждой операции рабочей нагрузки как потенциала для изменения/трансформации статического проекта структуры данных с учётом набора правил преобразования (Bentley, 1979; Bentley и Saxe, 1980; Scholten и Overmars, 1989; Overmars и Leeuwen, 1981; Leeuwen и Overmars, 1981; Leeuwen и Wood, 1980). Таким образом можно сгенерировать индивидуальный проект для конкретной рабочей нагрузки.

Расширяемые конструкции через абстракции: Hellerstein и др. (1995) предложили обобщённые деревья поиска (GiST) в качестве абстракции структуры данных. GiST предлагает API и шаблон кода, которые могут реализовать различные деревья поиска, чтобы адаптировать конструкцию к конкретному приложению. Для Например, GiST может вести себя как B⁺-дерево (Graefe, 2011), R-дерево (Guttman, 1984; Manolopoulos и др., 2006), RD-дерево (Hellerstein и др., 1995), или множество других вариаций древовидных индексов (таких как деревья частичных сумм (Wong и Easton, 1980), k-D-B-деревья (Robinson, 1981), Ch-деревья (Kim и др., 1989), hB-деревья (Lomet и Salzberg, 1990), V-деревья (Mediano и др., 1994) и TV-деревья (Lin и др., 1994)).

Грамматика структуры данных: другой подход к проектированию структуры данных — это подход, основанный на главных принципах, т. е. на минимально возможных проектных решениях, связанных с полным проектированием. Калькулятор данных (Idreos и др., 2018a; Idreos и др., 2018b) представляет такую грамматику структур данных, которая состоит из принципов проектирования и правил проектирования. Она показывает, что существует более 10 100 возможных конструкций структур данных ключ-значение. Кроме того, эта работа позволяет провести более тонкую классификацию конструкций и компромиссов (Athanassoulis и Idreos, 2016; Athanassoulis и др., 2016), а также предоставлять конструкции структур данных и код автоматически, используя структуры данных и код автоматически с помощью математического моделирования и алгоритмов поиска, основанных на машинном обучении (Idreos и др., 2019b).

Ротация и перебалансировка. Когда данные изменяются на месте и организация данных дополняется индексной структурой, эта индексная структура также должна быть обновлена, чтобы отразить новые позиции каждого элемента. Чтобы сохранить преимущества древовидного индексирования при вставках, удалениях и обновлениях, деревья динамического поиска требуют реорганизации, чтобы сохранить их сублинейную производительность. Варианты бинарных деревьев предлагают самобалансировку за счет ротации (Sedgewick, 1983). Два ярких примера: AVL-деревья (Adelson-Velsky и Landis, 1962) и красно-черные деревья (Bayer, 1972). Новые конструкции самовращающихся самобалансирующихся бинарных деревьев стремятся к тому, чтобы повороты затрагивали только локальную область (Haeupler и др., 2015).

Перебалансировка B⁺-деревьев. Деревья динамического поиска, которые имеют гораздо больше дочерних деревьев, такие как B⁺-деревья и их разновидности, поддерживают баланс путем разделения и слияния узлов для поддержки инварианта, согласно которому каждый узел будет заполнен не менее чем на 50% (Graefe, 2011; Ramakrishnan и Gehrke, 2002). Перебалансировка происходит в основном на нижнем уровне, и экспоненциально меньшее количество раз по мере продвижения к корню, что приводит к низкой амортизированной стоимости вставки. Кроме того, этот подход гарантирует, что дерево всегда будет сбалансированным, предлагая одинаковую (логарифмическую) длину пути для каждой части ключевой области (Bayer и McCreight, 1970; Comer, 1979).

Удаление в B⁺-деревьях. Хотя алгоритмы, описанные в учебниках для B⁺-деревьев включают объединение узлов, как описано выше, рабочие нагрузки, в которых вставок больше, чем удалений (даже немного больше), будут иметь тенденцию разделяться вскоре после слияния. В таких случаях вместо слияния узла n, когда в узле n более 50% пустого пространства, лучше подождать, пока n не станет пустым, а затем просто удалить его. Такой подход дает почти такое же использование при гораздо меньших затратах на обслуживание (Johnson и Shasha, 1989).

Многоверсионное индексирование. При обсуждении политики модификации в разделе 3.6, мы отметили, что модификации вне места создают многокопийную организацию данных, поскольку старые версии ключей-значений данного ключа остаются в структуре данных даже после того, как в неё попадают новые после их ввода. Хотя свойство многокопийности рассматривается в первую очередь как накладные расходы, приводящие к увеличению занимаемого пространства, как обсуждается в Dong и др. (2017), этот артефакт модификаций вне места обеспечивает (непреднамеренную) частичную поддержку многоверсионной организации данных, которая нацелена на хранение, индексирование и предоставление доступа к нескольким историческим версиям значений, связанных с заданным ключом. Журналоподобные структуры, которые явно поддерживают множественные версии, LHAM от Muth и др. (2000) или многоверсионные B⁺-деревья (Becker и др., 1996; Varman и Verma, 1997). Другие многоверсионные индексы для современного оборудования и HTAP включают (Gottstein и др., 2014; Riegger и др., 2017; Riegger и др., 2019; Riegger и др., 2020), которые используют дизайн LSM-деревьев (O'Neil и др., 1996) и разделенных B-деревьев (Graefe, 2003).