Для чего используется индекс

Индексы в PostgreSQL

Авторизуйтесь

Индексы в PostgreSQL

Full Stack Developer в DataArt

В статье я расскажу о предназначении и основах принципов работы объектов баз данных — индексов. На примере СУБД PostgreSQL коротко рассмотрим несколько разных типов индексов и классов задач, для которых они применимы. В конце материала поделюсь ссылками на статьи с более глубоким описанием внутреннего устройства индексов в PostgreSQL.

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

Предназначение индексов

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

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

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

В качестве примера рассмотрим задачу поиска в списке чисел. Используя перебор элементов списка, в худшем случае, нам придется просмотреть список целиком. Алгоритмическая сложность такого метода — O(n). Но если мы будем хранить наши числа особым образом — отсортированными по возрастанию или по убыванию — сможем использовать алгоритм бинарного поиска.

2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180

Допустим, необходимо определить, содержит ли этот отсортированный список число 158. Для этого:

В итоге метод бинарного поиска дал нам результат всего за три шага. При полном переборе с начала списка нам потребовалось бы 16 шагов. Бинарный поиск имеет алгоритмическую сложность O(log(n)). Используя формулы алгоритмической сложности O(n) и O(log(n)), мы можем оценить, как будет меняться приблизительное количество операций при поиске разными способами с ростом объема данных:

Результат впечатляет. Храня данные в отсортированном виде, мы не только снизили скорость поиска по ним, но и колоссально сократили скорость замедления поиска при росте объема данных.

Использование индексов в базе данных дает аналогичный результат. Принцип работы одного из важнейших индексов в базе данных (индекс на основе B-дерева) основан именно на рассмотренном нами выше принципе — возможности хранить данные в отсортированном виде.

Индексы в PostgreSQL

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

SELECT * FROM table_name WHERE P(column_name) = 1

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

Если мы хотим ускорить выполнение запроса, условие которого вычисляется по одной или нескольким колонкам, в PostgreSQL нам необходимо создать для этих колонок индекс с помощью команды CREATE INDEX :

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

Например, индекс может поддерживать ограничение на уникальность и не допускать появления в таблице нескольких строк, значения индексируемых столбцов у которых совпадают. Для этого при создании индекса указывают ключевое слово UNIQUE :

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

CREATE INDEX index_name ON table_name(lower(text_field))

И такой индекс уже может успешно применяться для ускорения нашего запроса.

CREATE INDEX index_name ON table_name USING GIST (column_name)

B-tree

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

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

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

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

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

Однако хранить индекс просто в виде отсортированного массива мы не можем, т. к. данные могут модифицироваться: значения могут меняться, записи — удаляться или добавляться. Чтобы эффективно поддерживать хранение индексируемых данных в отсортированном виде, индекс хранят в виде сбалансированного сильно ветвящегося дерева, называемого B-деревом (B-tree).

Корневой узел B-дерева содержит в упорядоченном виде несколько значений из общего набора, допустим, t элементов. Тогда все остальные элементы можно распределить по t+1 дочерним поддеревьям по следующему правилу:

Каждое поддерево, в свою очередь, тоже является B-деревом, имеет корневой элемент и строится далее рекурсивно по такому же принципу.

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

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

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

Индекс на основе B-дерева может ускорять запросы, которые используют не целиком входящие в индекс поля, а любую часть, начиная с начала. Например, индекс может ускорить запрос LIKE для поиска строк, которые начинаются с заданной подстроки:

SELECT * FROM table_name WHERE text_field LIKE ‘start_substring%’

Если индекс построен по нескольким колонкам, он может ускорять запросы, в которых фигурируют одна или несколько первых колонок. Поэтому важен порядок, в котором мы указываем колонки при создании индекса. Допустим, у нас есть индекс по колонкам col_1 и col_2. Тогда он может использоваться в том числе для ускорения запроса вида:

SELECT * FROM table_name WHERE col_1 = 123

И нам не нужно создавать отдельный индекс для колонки col_1. Будет использоваться составной индекс (col_1, col_2).

Однако для запроса только по колонке col_2 такой составной индекс уже использовать не получится.

Подробнее, как индекс на основе B-дерева реализован в PostgreSQL, см. статью.

GiST и SP-GiST

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree. Но b-tree применимо только к тем типам данных, для которых имеет смысл операция сравнения и есть возможность упорядочивания. Но PostgreSQL позволяет хранить и такие данные, для которых операция упорядочивания не имеет смысла, например, геоданные и геометрические объекты.

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

Например, в GiST-индекс можно уложить R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. д.). Такой индекс доступен в PostgreSQL и может быть полезен при разработке геоинформационных систем, в которых возникают запросы вида «получить множество объектов на карте, находящихся от заданной точки на расстоянии не более 1 км».

SP-GiST похож GiST, но он позволяет создавать несбалансированные деревья. Такие деревья могут быть полезны при разбиении множества на непересекающиеся объекты. Буквы SP означают space partitioning. К такому типу индексов можно отнести kd-деревья, реализация которых присутствует в PostgreSQL. Его, как и R-дерево, можно использовать для ускорения запросов геометрического поиска. Свойство непересечения упрощает принятие решений при вставке и поиске. С другой стороны, получающиеся деревья, как правило, слабо ветвисты, что усложняет их эффективное хранение во внешней памяти.

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

Подробнее об алгоритмах, лежащих в основе R- и kd-деревьев см. раз и два, а об их реализации и использовании в PostgreSQL см. в этой и этой статье.

Заключение

Индексы — важнейший инструмент баз данных, ускоряющий поиск. Он не бесплатен, создавать много индексов без лишней необходимости не стоит — индексы занимают дополнительную память, и при любом обновлении проиндексированных данных СУБД должна выполнять дополнительную работу по поддержанию индекса в актуальном состоянии.

PostgreSQL поддерживает разные типы индексов для разных задач:

Источник

Что такое фондовые индексы

Биржевой индекс — это виртуальный набор активов, собранный по какому-то признаку. Чаще всего это ценные бумаги, но могут быть и биржевые товары.

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

Разберу, зачем нужны индексы, какие они бывают и как в них инвестировать.

Зачем нужны индексы и откуда они берутся

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

Как и цена акций и иных активов, значение индекса меняется много раз за день. Например, некий индекс состоит из акций крупных компаний США. Часть бумаг за день дорожает, часть — дешевеет, а цена некоторых не меняется.

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

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

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

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

Какие бывают индексы

Индексов много — сотни и тысячи. Их можно классифицировать по многим параметрам. Назову основные.

По виду активов. Индексы акций состоят из акций, то есть долей в компаниях. Акции — довольно рискованный актив, так что такие индексы волатильны: их доходность сложно предсказать, а значение за день может вырасти или упасть на несколько процентов.

Индексы облигаций отслеживают состояние долгового рынка. Обычно такие индексы колеблются меньше, чем индексы акций, но и доходность в долгосрочной перспективе в среднем ниже.

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

Есть также индексы денежного рынка, индексы волатильности и даже криптовалютные индексы.

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

Например, существует индекс акций российских строительных компаний, в котором бумаги всего четырех компаний. Есть индекс FTSE Actuaries UK Index Linked Gilts Over 5 Years — индекс гособлигаций Великобритании с привязкой к инфляции, до погашения которых более пяти лет.

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

Например, в индексе MSCI AC Asia ex Japan есть акции двух развитых и девяти развивающихся стран Азии, при этом оттуда исключена Япония. В индекс FTSE Global All Cap входят акции более 9000 компаний из почти 50 стран мира.

Может учитываться не только капитализация, но и доля акций в свободном обращении — так называемый коэффициент фри-флоат. Этот параметр применяется в том же S&P 500 и индексе Московской биржи.

Еще может искусственно ограничиваться максимальный вес одной бумаги. Так, в индексе Московской биржи доля акций одной компании не может превышать 15% на момент формирования базы расчета индекса, а в остальное время не может превышать 30%. Топ-5 составляющих не могут занимать более 55 и 60% индекса соответственно.

Приложение № 3 к Методике расчета индексов акций Московской биржи от 18.01.2021DOCX, 153 КБ

Взвешивание по капитализации удобно тем, что не надо постоянно корректировать состав индекса. Акции подорожали, из-за чего выросла капитализация компании — и автоматически выросла доля акции в индексе.

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

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

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

Может использоваться даже ВВП стран, если речь о государственных облигациях. Последний подход применяется в индексе Solactive GDP Weighted Global Government Bond.

Статья Solactive о взвешивании индексов облигаций по ВВПPDF, 442 КБ

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

Еще есть индексы полной доходности, или total return. Они учитывают не только изменение цены, но и дивиденды или купоны. Если инвестор хочет оценить доходность какого-то вида активов, особенно в долгосрочной перспективе, лучше смотреть на индекс полной доходности.

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

Например, есть ценовой индекс Московской биржи — без учета дивидендов от акций. В дополнение к нему рассчитываются индексы полной доходности:

Как вложиться в индекс

Купить долю в индексе нельзя, потому что индекс — это условное понятие. Но можно инвестировать на основе индекса.

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

Вот несколько способов инвестировать на основе индекса.

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

Кроме того, ручное повторение индекса не очень удобно из-за затрат времени на покупку и продажу десятков и сотен бумаг. Еще это может быть менее выгодно из-за налогов.

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

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

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

Купить паи фонда. Оптимальный способ — купить долю в инвестиционном фонде, то есть в ETF или биржевом ПИФе, отслеживающем нужный вам индекс. Долю в фонде называют паем или акцией. В фонде содержатся бумаги из индекса в нужных пропорциях, и если у инвестора есть паи фонда, то у него есть кусочек всех активов.

Цена пая зависит от того, как меняется стоимость активов в фонде. Например, если фонд отслеживает индекс S&P 500 и акции в составе индекса и фонда в среднем выросли, цена пая увеличится. Если индекс падает, пай тоже будет дешеветь.

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

Через российских брокеров можно совершать сделки с ETF и БПИФами на Московской бирже. Через них же можно получить доступ к фондам на иностранных биржах, но понадобится статус квалифицированного инвестора.

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

Примеры биржевых индексов

Вот несколько примеров индексов и фондов, которые их отслеживают. Это не инвестиционная рекомендация.

Индекс акций крупнейших компаний США и один из самых важных индексов в мире. В него входят 505 акций, а не 500, потому что несколько компаний представлены в индексе не одной акцией. Наибольший вес — у акций Apple, Microsoft и Amazon.

Кто рассчитывает: S&P Dow Jones Indices.

Подходящие фонды на Московской бирже: TMOS, AKSP, RCUS, SBSP, VTBA. Также по смыслу очень близок FXUS, хоть и отслеживает иной индекс.

Подходящие фонды на зарубежных биржах: SPY, CSPX.

Индекс акций крупнейших нефинансовых компаний, чьи акции торгуются на бирже Nasdaq. В составе индекса — 103 бумаги 100 компаний, большинство из них американские. Наибольший вес у акций Apple, Microsoft и Amazon.

Кто рассчитывает: биржа Nasdaq.

Подходящие фонды на Московской бирже: AKNX.

Подходящие фонды на зарубежных биржах: QQQ, CNDX.

Индекс акций США. В нем примерно 4000 бумаг компаний всех размеров из всех секторов. Все акции из состава S&P 500 и Nasdaq-100 есть и в этом индексе.

Кто рассчитывает: Center for Research in Security Prices.

Подходящие фонды на Московской бирже: нет.

Подходящие фонды на зарубежных биржах: VTI.

Индекс акций крупнейших компаний России. В составе индекса — 43 акции и депозитарные расписки 40 компаний, наибольшая доля у «Газпрома», Сбербанка и «Лукойла».

Еще есть индекс RTS. Он состоит из тех же бумаг, что и индекс Мосбиржи, но рассчитывается в долларах.

Кто рассчитывает: Московская биржа.

Подходящие фонды на зарубежных биржах: нет, но есть близкие по смыслу, например RSX и ERUS. У них отличается состав из-за того, что они отслеживают другие индексы.

Индекс акций мира согласно капитализации рынков, то есть отдельных стран. В составе — около 9100 акций компаний из почти 50 развитых и развивающихся стран: от США, Японии и Великобритании до Бразилии, Малайзии и Турции. Вес США — около 60% индекса.

Кто рассчитывает: FTSE Russell.

Подходящие фонды на Московской бирже: нет.

Подходящие фонды на зарубежных биржах: VT. Также по смыслу близок VWRA, но у него немного другой индекс и меньше бумаг в составе.

Индекс облигаций федерального займа. В составе — 24 наименования ОФЗ с постоянным купоном и разными датами погашения.

Кто рассчитывает: Московская биржа.

Подходящие фонды на Московской бирже: SBGB.

Подходящие фонды на зарубежных биржах: нет.

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

У этого индекса есть версии с хеджированием в разные валюты, например доллары и евро. Благодаря валютному хеджированию изменение курсов валют не влияет на результат инвестиций.

Кто рассчитывает: Bloomberg.

Подходящие фонды на Московской бирже: нет.

Подходящие фонды на зарубежных биржах: AGGU, GLAD, SPFE.

«Всепогодный» индекс, основанный на идее постоянного портфеля американского экономиста Гарри Брауна. В его составе по 25% занимают акции 15 крупных российских компаний, долгосрочные ОФЗ, краткосрочные ОФЗ и золото.

Кто рассчитывает: Тинькофф.

Подходящие фонды на Московской бирже: TRUR.

Подходящие фонды на зарубежных биржах: нет.

Источник