Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL

    В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД

    B-Tree


    Семейство B-Tree индексов — это наиболее часто используемый тип индексов, организованных как сбалансированное дерево, упорядоченных ключей. Они поддерживаются практически всеми СУБД как реляционными, так нереляционными, и практически для всех типов данных.



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

    Пространственные индексы


    В данный момент все данные СУБД имеют пространственные типы данных и функции для работы с ними, для Oracle — это множество типов и функций в схеме MDSYS, для PostgreSQL — point, line, lseg, polygon, box, path, polygon, circle, в MySQL — geometry, point, linestring, polygon, multipoint, multilinestring, multipolygon, geometrycollection, MS SQL — Point, MultiPoint, LineString, MultiLineString, Polygon, MultiPolygon, GeometryCollection.
    В схеме работы пространственных запросов обычно выделяют две стадии или две ступени фильтрации. СУБД, обладающие слабой пространственной поддержкой, отрабатывают только первую ступень (грубая фильтрация, MySQL). Как правило, на этой стадии используется приближенное, аппроксимированное представление объектов. Самый распространенный тип аппроксимации – минимальный ограничивающий прямоугольник (MBR – Minimum Bounding Rectangle) [100].
    Для пространственных типов данных существуют особые методы индексирования на основе R-деревьев(R-Tree index) и сеток(Grid-based Spatial index).

    Spatial grid

    Spatial grid(пространственная сетка) index – это древовидная структура, подобная B-дереву, но используется для организации доступа к пространственным(Spatial) данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами(широтой и долготой). В этой структуре узлами дерева выступают ячейки пространства. Например, для двухмерного пространства: сначала вся родительская площадь будет разбита на сетку строго определенного разрешения, затем каждая ячейка сетки, в которой количество объектов превышает установленный максимум объектов в ячейке, будет разбита на подсетку следующего уровня. Этот процесс будет продолжаться до тех пор, пока не будет достигнут максимум вложенности (если установлен), или пока все не будет разделено до ячеек, не превышающих максимум объектов.


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


    Quadtree

    Quadtree – это подвид Grid-based Spatial index, в котором в родительской ячейке всегда 4 потомка и разрешение сетки варьируется в зависимости от характера или сложности данных.



    R-Tree

    R-Tree (Regions Tree) – это тоже древовидная структура данных подобная Spatial Grid, предложенная в 1984 году Антонином Гуттманом. Эта структура данных тоже разбивает пространство на множество иерархически вложенных ячеек, но которые, в отличие от Spatial Grid, не обязаны полностью покрывать родительскую ячейку и могут пересекаться.
    Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: с квадратичной и линейной сложностью(Гуттман, конечно, описал и с экспоненциальной сложностью — Exhaustive Search, но он, естественно, нигде не используется).
    Квадратичный подтип заключается в разбиении на два прямоугольника с минимальной площадью, покрывающие все объекты. Линейный – в разбиении по максимальной удаленности.



    HASH


    Hash-индексы были предложены Артуром Фуллером, и предполагают хранение не самих значений, а их хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается скорость их обработки) индексов из больших полей. Таким образом, при запросах с использованием HASH-индексов, сравниваться будут не искомое со значения поля, а хэш от искомого значения с хэшами полей.
    Из-за нелинейнойсти хэш-функций данный индекс нельзя сортировать по значению, что приводит к невозможности использования в сравнениях больше/меньше и «is null». Кроме того, так как хэши не уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.

    Bitmap


    Bitmap index – метод битовых индексов заключается в создании отдельных битовых карт (последовательность 0 и 1) для каждого возможного значения столбца, где каждому биту соответствует строка с индексируемым значением, а его значение равное 1 означает, что запись, соответствующая позиции бита содержит индексируемое значение для данного столбца или свойства.

    EmpID Пол
    1 Мужской
    2 Женский
    3 Женский
    4 Мужской
    5 Женский


    Битовые карты
    Значение Начало Конец Битовая маска
    Мужской Адрес первой строки Адрес последней строки 10010
    Женский Адрес первой строки Адрес последней строки 01101

    Основное преимущество битовых индексов в том, что на больших множествах с низкой мощностью и хорошей кластеризацией по их значениям индекс будет меньше чем B*-tree. (Подробнее стоит прочесть здесь или здесь)

    Reverse index


    Reverse index – это тоже B-tree индекс но с реверсированным ключом, используемый в основном для монотонно возрастающих значений(например, автоинкрементный идентификатор) в OLTP системах с целью снятия конкуренции за последний листовой блок индекса, т.к. благодаря переворачиванию значения две соседние записи индекса попадают в разные блоки индекса. Он не может использоваться для диапазонного поиска.
    Пример:
    Поле в таблице(bin) Ключ reverse-индекса(bin)
    00000001 10000000
    00001001 10010000
    00001010 01010000
    00001011 11010000
    Как видите, значение в индексе изменяется намного больше, чем само значение в таблице, и поэтому в структуре b-tree, они попадут в разные блоки.

    Inverted index


    Инвертированный индекс – это полнотекстовый индекс, хранящий для каждого лексемы ключей отсортированный список адресов записей таблицы, которые содержат данный ключ.
    1 Мама мыла раму
    2 Папа мыл раму
    3 Папа мыл машину
    4 Мама отполировала машину

    В упрощенном виде это будет выглядеть так:
    Мама 1,4
    Мыла 1
    Раму 1,2
    Папа 2,3
    Отполировала 4
    Машину 3,4


    Partial index


    Partial index — это индекс, построенный на части таблицы, удовлетворяющей определенному условию самого индекса. Данный индекс создан для уменьшения размера индекса.

    Function-based index


    Самим же гибким типом индексов являются функциональные индексы, то есть индексы, ключи которых хранят результат пользовательских функций. Функциональные индексы часто строятся для полей, значения которых проходят предварительную обработку перед сравнением в команде SQL. Например, при сравнении строковых данных без учета регистра символов часто используется функция UPPER. Создание функционального индекса с функцией UPPER улучшает эффективность таких сравнений.
    Кроме того, функциональный индекс может помочь реализовать любой другой отсутствующий тип индексов данной СУБД(кроме, пожалуй, битового индекса, например, Hash для Oracle)

    Сводная таблица типов индексов


    MySQL PostgreSQL MS SQL Oracle
    B-Tree index Есть Есть Есть Есть
    Поддерживаемые пространственные индексы(Spatial indexes) R-Tree с квадратичным разбиением Rtree_GiST(используется линейное разбиение) 4-х уровневый Grid-based spatial index (отдельные для географических и геодезических данных) R-Tree c квадратичным разбиением; Quadtree
    Hash index Только в таблицах типа Memory Есть Нет Нет
    Bitmap index Нет Есть Нет Есть
    Reverse index Нет Нет Нет Есть
    Inverted index Есть Есть Есть Есть
    Partial index Нет Есть Есть Нет
    Function based index Нет Есть Есть Есть

    Стоит упомянуть, что в PostgreSQL GiST позволяет создать для любого собственного типа данных индекс основанный на R-Tree. Для этого нужно реализовать все 7 функций механизма R-Tree.

    Дополнительно можно прочитать здесь:
    Oracle Spatial User's Guide and Reference
    Пространственные данные в MS SQL
    MS SQL: Spatial Indexing Overview
    Hilbert R-tree
    Пространственные типы PostgreSQL
    Пространственные функции PostgreSQL
    Индексирование пространственных данных в СУБД Microsoft SQL Server 2000
    Papadias D., Theodoridis T. Spatial Relations, Minimum Bounding Rectangles and Spatial Data Structures // Technical Report KDB-SLAB-TR-94-04,
    Faloutsos C., Kamel I. Hilbert R-Tree: An Improved R-Tree UsingFractals // Department of CS, University of Maryland, TechnicalResearch Report TR-93-19,
    Wikipedia: Hilbert R-tree
    Методы поиска во внешней памяти
    Артур Фуллер. Intelligent database design using hash keys

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

    Подробнее
    Реклама
    Комментарии 41
    • +6
      B-Tree индексов — это наиболее часто используемый тип индексов, организованных как обычное бинарное дерево


      B-Tree — вовсе не бинарное дерево, вы что?
      • 0
        Да, спасибо, поправил. Этот пункт просто многим знаком, т.к. используется повсеместно с небольшими вариациями.
      • +1
        Хотелось бы по подробнее узнать, для каких случаев какие индексы лучше выбрать.
        • +3
          Это довольно большой объем нетривиальной информации будет, в следующих статьях постараюсь затронуть как можно больше различных вариантов.
          • 0
            Спасибо, ждём с нетерпением.
          • +2
            Поддержу. Хотелось бы узнать плюсы и минусы разных типов индексов.
            • 0
              Тут вопрос в том, что еще нужно решать — а стоит ли использовать индексы в конкретной таблице.
              Я в одной таблице задал только Primary key и все. Ибо в нее идет только запись. Когда там было еще пару индексов — мускуль вешался неплохо… Таблица уже гига полтора весит. Индексы нужны были на varchar полях.
              • +4
                А зачем создавать индексы в таблице где идёт только запись?
                • +6
                  А зачем создавать таблицы где идёт только запись?
                • 0
                  Primary key создает неявный B-Tree индекс. По крайней мере Oracle делает это.
                  • 0

                    все зависит от СУБД. тот же MS SQL обычно формирует кластерный индекс, если не сказано иначе.

              • 0
                По поводу отсутствия Hash index в Оракле — имхо, довольно странно, т.к. Query Optimizer-у можно намекнуть, чтобы он сделал HASH-индекс одной таблицы, и потом join-ил её с другой по хешу.
                • 0
                  И Oracle и MS SQL умеют джойнить с использованием хэшейuse_hash, например), но не имеют таких постоянных индексов.
                • +1
                  Полезно, спасибо. Но, всё-таки, очень хочется увидеть развёрнутое описание каждого типа индексов. Понятно, что всё это есть в документации, но в большинстве случаев информация в ней слишком размазана по разным главам, поэтому компиляция инфы по одной теме в одном документе всегда очень полезна. Может возьмётесь, раз начали? «И моя благодарность не будет иметь границ в разумных пределах» (ц)
                  • 0
                    Развёрнутое описание каждого типа индексов, превышающее по информативности официальную документацию — можно получить только описав практическое применение того или иного типа индексов в том или ином своём проекте. Не факт что автор использовал все описанные им типы индексов в практических разработках живых БД. Я к примеру битмапами ещё не пользовался (как впрочем и Spatial grid и R-tree)
                  • 0
                    Отличный обзор, спасибо!
                    • 0
                      У постгресса нет bitmat index'ов, однако он может строить такие структуры в памяти при выполнении запроса
                      • 0
                        В MSSQL в индексе можно указать обратную сортировкую, наверное это и есть Reverse index?
                        • 0
                          нет, обратная сортировка это именно сортировка, а смысл реверсивного индекса — раскидать по разным блокам близлежащие значения. Обычно строят на полях которые монотонно возрастают (sequence, identity, date-time). Собственно в статье написано как именно меняется ключ для индекса.
                          • 0
                            Ну так это кластерный индекс с обратной сортировкой. Я пока реально не улавливаю разницу.
                            • 0
                              Нет, это разные вещи. Индексы с обратной сортировкой есть во всех этих СУБД, кроме PostgreSQL, т.к. там они не нужны — у них предусмотрен просмотр индекса в обратном порядке. Добавил уточнение с примером.
                        • 0
                          В PostgreSQL можно запросто организовать reverse index. Для этого достаточно сделать свою функцию сравнения (которая сравнивает в перевернутом порядке), а на основе неё класс операторов для btree, и использовать этот класс операторов для индекса.
                          • 0
                            Да, можно и не сложно, но нужно будет изменить все 7 функций, и он в postgreSQL не нужен.
                            • 0
                              Не 7, а 5: это же btree, а не gist. А почему не нужен?
                              • 0
                                Да 5, ошибся на автомате. Ну потому, что проще сделать function-based индекс, где функцией и будет реверс ключа
                          • 0
                            Вопрос про Inverted index в Oracle. Имеется ввиду Oracle Text??
                          • 0
                            Я бы еще добавил partial index из Postgre SQL, пример из доки:

                            CREATE INDEX access_log_client_ip_ix ON access_log (client_ip)
                            WHERE NOT (client_ip > inet '192.168.100.0' AND client_ip < inet '192.168.100.255');

                            A typical query that can use this index would be:

                            SELECT * FROM access_log WHERE url = '/index.html' AND client_ip = inet '212.78.10.32';
                            • 0
                              Добавил, но он есть только в PostgreSQL, в Oracle и MS SQL может быть сделан с помощью функциональных индексов, правда чуть большего размера.
                              • 0
                                Как можно сделать частичный индекс с помощью функционального?
                                • 0
                                  Создав функциональный индекс, который при удовлетворяющих условию значениях будет возвращать само значение, в противном случае одинаковое маленькое заранее опреденное значение. Таким образом индекс станет меньше чем обычный как по размеру самих данных, так и по количеству в нем ветвей, но, конечно, он будет побольше.
                                  • 0
                                    Непонятно почему он меньше-то станет, указатели на все ряды с маленьким значением всё равно будут в нём хранится. И насколько это будет быстро работать?
                                    • 0
                                      Указатели на неудовлетворящие условию ряды будут, но все они будут в одном листе дерева.
                                      Например, пусть есть таблица полем id заполненным от 1 до 1000000. Создаем функциональный индекс возвращающий -1 для всех кроме диапазона от 1 до 100. В таком случае у нас дерево для индекса будет высотой всего в 7 вместо 20
                            • 0
                              Хорошая статья.

                              Также очень интересно узнать о практическом применении этих знаний — лично Вашем. То есть какие БД вы разрабатывали, их размер (по разным критериям), какая нагрузка на них была, на какой СУБД, где Вы использовали тот или иной тип индекса. Какие выбирали решения при проектировании структуры БД и прочее прочее прочее… Эта тема достаточно интересна, но малопопулярна на хабре.

                              К примеру — как лучше реализовать диапазонный поиск (индекс) для диапазонных значений (если вы сталкивались с такой задачей)…
                              • 0
                                Подробнее опишу в следующих статьях, а сейчас вкратце насчет диапазонного поиска:
                                В таком случае есть три наиболее ярких варианта, если для простоты рассматривать только оптимизацию под большое количество select'ов:
                                1) Большое количество разных значений и они равномерно распределены
                                2) Большое количество разных значений и они очень неравномерно распределены(допустим, несколько значений у 90% записей)
                                3) Малое количество разных значений относительно общего количество записей

                                В первом варианте лучше всего будет «index organized»(это для Oracle, в MS SQL она называется clustered table) таблица секционированная по кластерному b-tree индексу. Таки образом и сама таблица будет отсортирована и поиск будет быстрее, т.к. после поиска первого значения будет использоваться проход по нижним листам дерева.

                                Во-втором варианте, скорее всего будет лучше использовать bitmap индекс, несмотря на то, что обычно его не советуют для диапазонного поиска. Дело в том, что поиск 90% записей будет проводиться гораздо быстрее, следовательно, при равномерном разбросе диапазонов запросов в 90% случаев будет быстрее чем b-tree

                                В-третьем варианте нюансов будет побольше и следовало бы оценить все факторы.Вот здесь подробнее, почему
                                • 0
                                  я имел ввиде не самостоятельный диапазонный поиск а именно для диапазонных значений, к примеру пользователь задал цену покупки от 1000 до 10000 и ему необходимо показать се предложения в этом диапазоне, а собственно продавцы задают чёткое значение. Я этузадачу решил, но интересно услышать ваш вариант…
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • 0
                                  Подскажите, можно ли сделать какие-либо выводы относительно выбора той или иной субд исходя из представленной таблицы Сводная таблица типов индексов?
                                  Что-то вроде «для решения таких-то задач лучше такие-то индексы, а вот эта и эта суд их не поддерживает, поэтому при прочих равных лучше вот эту субд».
                                  • 0
                                    в PostgreSQL нет bitmap индексов. Есть bitmap index scan, который используется при выполнении запросов, чтобы упорядочивать записи по физическому расположению и чтобы пересекать/объединять результаты поиска по нескольким индексам

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.