Войти
A индекс растрового изображения - это особый вид индекса базы данных, который использует растровые изображения.
Растровые индексы традиционно считались хорошо работающими для столбцов с низким количеством , которые имеют небольшое количество различных значений, абсолютно или относительно количества записей, содержащих данные.. Крайний случай низкой мощности - это логические данные (например, есть ли у жителя города доступ в Интернет?), У которого есть два значения: True и False. Индексы растровых изображений используют битовые массивы (обычно называемые растровыми изображениями) и отвечают на запросы, выполняя побитовые логические операции с этими растровыми изображениями. Индексы Bitmap имеют значительное преимущество в пространстве и производительности по сравнению с другими структурами для запроса таких данных. Их недостатком является то, что они менее эффективны, чем традиционные индексы B-tree для столбцов, данные которых часто обновляются: следовательно, они чаще используются в системах только для чтения, которые специализируются на быстрых запросах - например, данные склады и, как правило, не подходят для приложений онлайн-обработки транзакций.
Некоторые исследователи утверждают, что растровые индексы также полезны для данных с умеренным или даже большим количеством элементов (например, данных с уникальными значениями), доступ к которым осуществляется только для чтения, а запросы обращаются к нескольким столбцам с растровым индексом, используя широко используются операторы AND, OR или XOR.
Растровые индексы также полезны в приложениях хранилищ данных для присоединения к большой таблице фактов в меньшие таблицы измерений, например, организованные в звездообразную схему.
Представление на основе растрового изображения также можно использовать для представления структуры данных, которая помечена и направлена атрибутированным мультиграфом, используемым для запросов в базы данных графов.Эффективное управление графами на основе индексов растровых изображений В статье показано, как можно использовать представление индексов растровых изображений для управления большим набором данных (миллиарды точек данных) и эффективного ответа на запросы, связанные с графом.
Продолжая пример доступа к Интернету, индекс растрового изображения можно логически рассматривать следующим образом:
| Идентификатор | HasInternet | Растровые изображения | |
|---|---|---|---|
| Y | N | ||
| 1 | Да | 1 | 0 |
| 2 | No | 0 | 1 |
| 3 | No | 0 | 1 |
| 4 | Не указано | 0 | 0 |
| 5 | Да | 1 | 0 |
Слева Идентификатор относится к уникальному номеру, присвоенному каждому резиденту, HasInternet - это данные, которые необходимо проиндексировать, содержимое индекса растрового изображения отображается в виде двух столбцов под заголовком растровые изображения. Каждый столбец на левой иллюстрации представляет собой растровое изображение в индексе растрового изображения. В этом случае есть два таких растровых изображения, одно для «есть интернет» Да и одно для «есть интернет» Нет. Легко видеть, что каждый бит в растровом изображении Y показывает, относится ли конкретная строка к человеку, имеющему доступ в Интернет.. Это простейшая форма растрового индекса. Большинство столбцов будут иметь более разные значения. Например, сумма продаж, вероятно, будет иметь гораздо большее количество различных значений. Вариации индекса растрового изображения также могут эффективно индексировать эти данные. Кратко рассмотрим три таких варианта.
Примечание: многие из цитируемых здесь ссылок приведены в (John Wu (2007)). Для тех, кому может быть интересно поэкспериментировать с некоторыми из упомянутых здесь идей, многие из них реализованы в программном обеспечении с открытым исходным кодом, таком как FastBit, библиотека Lemur Bitmap Index C ++, библиотека Java Roaring Bitmap и Apache Hive Система хранилищ данных.
По историческим причинам сжатие растровых изображений и сжатие инвертированного списка были разработаны как отдельные направления исследований, и только позже были признаны решающими, по сути, одну и ту же проблему.
Программное обеспечение может сжимать каждое растровое изображение в растровом индексе для экономии места. По этой теме проделана значительная работа. Хотя есть исключения, такие как ревущие растровые изображения, алгоритмы сжатия растровых изображений обычно используют кодирование длин серий, например код растрового изображения с выравниванием по байтам, гибридный код с выравниванием по словам, гибридный гибрид с разделением по словам (PWAH) сжатие, гибридное выравнивание по словам списка позиций, сжатый адаптивный индекс (COMPAX), расширенный гибридный гибрид с выравниванием по словам (EWAH) и COmpressed 'N' Composable Integer SEt. Эти методы сжатия требуют очень небольших усилий для сжатия и распаковки. Что еще более важно, растровые изображения, сжатые с помощью BBC, WAH, COMPAX, PLWAH, EWAH и CONCISE, могут напрямую участвовать в побитовых операциях без декомпрессии. Это дает им значительные преимущества по сравнению с обычными методами сжатия, такими как LZ77. Сжатие BBC и его производные используются в коммерческой системе управления базами данных . BBC эффективен как для уменьшения размеров индекса, так и для поддержания производительности запросов. BBC кодирует растровые изображения в байтах, тогда как WAH кодирует словами, что лучше соответствует текущим ЦП. «Как для синтетических данных, так и для реальных данных приложений новые схемы с выравниванием слов используют только на 50% больше места, но выполняют логические операции со сжатыми данными в 12 раз быстрее, чем BBC». Сообщалось, что растровые изображения PLWAH занимают 50% дискового пространства, занимаемого растровыми изображениями WAH, и обеспечивают до 20% более высокую производительность при логических операциях. Аналогичные соображения можно сделать для CONCISE и Enhanced Word-Aligned Hybrid.
Производительность таких схем, как BBC, WAH, PLWAH, EWAH, COMPAX и CONCISE, зависит от порядка строк. Простая лексикографическая сортировка может разделить размер индекса на 9 и ускорить его в несколько раз. Чем больше таблица, тем важнее сортировать строки. Также были предложены методы перестановки для достижения тех же результатов сортировки при индексировании потоковых данных.
Базовые индексы битовой карты используют одну битовую карту для каждого отдельного значения. Можно уменьшить количество используемых растровых изображений, используя другой метод кодирования. Например, можно кодировать C различных значений, используя точечные рисунки журнала (C) с двоичным кодированием.
. Это уменьшает количество растровых изображений, дополнительно экономя место, но для ответа на любой запрос большинство растровых изображений должны быть доступ. Это делает его потенциально не таким эффективным, как сканирование вертикальной проекции базовых данных, также известной как материализованное представление или индекс проекции. Поиск оптимального метода кодирования, который уравновешивает (произвольную) производительность запроса, размер индекса и обслуживание индекса, остается сложной задачей.
Не принимая во внимание сжатие, Чан и Иоаннидис проанализировали класс методов многокомпонентного кодирования и пришли к выводу, что двухкомпонентное кодирование находится на изломе кривой зависимости производительности от размера индекса и, следовательно, представляет собой лучший вариант. -off между размером индекса и производительностью запроса.
Для столбцов с большим количеством элементов полезно разделить значения, где каждый лоток охватывает несколько значений, и построить растровые изображения для представления значений в каждом бункере. Такой подход уменьшает количество используемых растровых изображений независимо от метода кодирования. Однако сгруппированные индексы могут отвечать только на некоторые запросы без изучения базовых данных. Например, если корзина охватывает диапазон от 0,1 до 0,2, тогда, когда пользователь запрашивает все значения меньше 0,15, все строки, попадающие в корзину, являются возможными попаданиями и должны быть проверены, чтобы проверить, действительно ли они меньше 0,15.. Процесс проверки базовых данных известен как проверка кандидата. В большинстве случаев время, используемое для проверки кандидата, значительно больше, чем время, необходимое для работы с индексом битовой карты. Следовательно, индексы с группировкой показывают нестабильную производительность. Они могут быть очень быстрыми для некоторых запросов, но намного медленнее, если запрос не точно соответствует корзине.
Концепция растрового индекса была впервые представлена профессорами Израилем Шпиглером и Рафи Мааяном в их исследовании «Вопросы хранения и извлечения баз двоичных данных», опубликованном в 1985 году. Первая коммерческая база данных Продуктом для реализации растрового индекса была модель 204 американской корпорации Computer Corporation. Патрик О'Нил опубликовал статью об этой реализации в 1987 году. Эта реализация представляет собой гибрид между базовым индексом растрового изображения (без сжатия) и списком идентификаторов строк (список RID). В целом индекс организован в виде B + дерева. Когда мощность столбца низка, каждый листовой узел B-дерева будет содержать длинный список RID. В этом случае для представления списков RID в виде растровых изображений требуется меньше места. Поскольку каждое растровое изображение представляет одно отдельное значение, это базовый индекс растрового изображения. По мере увеличения числа столбцов каждое растровое изображение становится разреженным, и для хранения растровых изображений может потребоваться больше дискового пространства, чем для хранения того же содержимого, что и списки RID. В этом случае он переключается на использование списков RID, что делает его B+tree index.
Одна из самых веских причин для Использование растровых индексов заключается в том, что полученные из них промежуточные результаты также являются растровыми изображениями и могут быть эффективно повторно использованы в дальнейших операциях для ответа на более сложные запросы. Многие языки программирования поддерживают это как структуру данных битового массива. Например, в Java есть класс BitSet .
Некоторые системы баз данных, которые не предлагают постоянные индексы растровых изображений, используют растровые изображения внутри для ускорения обработки запросов. Например, в PostgreSQL версии 8.1 и более поздних версиях реализована оптимизация "сканирования индекса по битовой карте" для ускорения произвольно сложных логических операций между доступными индексами в одной таблице.
Для таблиц с большим количеством столбцов общее количество различных индексов, удовлетворяющих всем возможным запросам (с условиями фильтрации равенства для любого из полей), растет очень быстро и определяется следующей формулой:
![{\ displaystyle \ mathbf {C} _ {n} ^ {\ left [{\ frac {n} {2}} \ right]} \ Equiv {\ frac {n!} {\ left (n- \ left [{\ frac {n} {2}} \ right] \ right)! \ left [{\ frac {n} {2}} \ right]!}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9160ac60d370e6a8b56c98a5ca0d30e8679b89d5)
.Сканирование растрового индекса объединяет выражения для разных индексов, таким образом требуется только один индекс для каждого столбца для поддержки всех возможных запросов к таблице.
Применение этой стратегии доступа к индексам B-дерева также позволяет комбинировать запросы диапазона для нескольких столбцов. В этом подходе создается временная битовая карта в памяти с одним битом для каждой строки в таблице (1 MiB, таким образом, может хранить более 8 миллионов записей). Затем результаты каждого индекса объединяются в битовую карту с помощью побитовых операций. После оценки всех условий растровое изображение содержит «1» для строк, соответствующих выражению. Наконец, растровое изображение просматривается и выбираются совпадающие строки. В дополнение к эффективному объединению индексов это также улучшает локальность ссылки при доступе к таблице, поскольку все строки последовательно выбираются из основной таблицы. Внутреннее растровое изображение отбрасывается после запроса. Если в таблице слишком много строк для использования 1 бита на строку, вместо этого создается растровое изображение с потерями, с одним битом на страницу диска. В этом случае растровое изображение используется только для определения страниц для выборки; затем критерии фильтрации применяются ко всем строкам на соответствующих страницах.
| journal =()| journal =()