Индекс (базы данных)

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

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

Архитектура

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

Индексы могут быть реализованы различными структурами. Наиболее частоупотребимы B*-деревья, B+-деревья, B-деревья и хеши.

Последовательность столбцов в составном индексе

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

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

Производительность

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

Ограничения

Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмём такой запрос SQL:

SELECT first_name FROM people WHERE last_name = 'Франкенштейн';.

Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полное сканирование таблицы», в плане может отображаться словом NATURAL). При использовании индекса СУБД просто проходит по B-дереву, пока не найдёт запись «Франкенштейн». Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.

Теперь возьмём такой запрос:

SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';.

Этот запрос должен нам найти всех клиентов, у которых е-мейл заканчивается на @yahoo.com, однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по B-дереву. Эта проблема может быть решена созданием дополнительного индекса по выражению reverse(email_address) и формированием запроса вида:

SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@yahoo.com');.

В данном случае символ подстановки окажется в самой правой позиции (moc.oohay@%), что не исключает использование индекса по reverse(email_address).

Разреженный индекс

Разреженный индекс (англ. sparse index) в базах данных — это файл с последовательностью пар ключей и указателей. Каждый ключ в разреженном индексе, в отличие от плотного индекса, ассоциируется с определённым указателем на блок в сортированном файле данных. Идея использования индексов пришла оттого, что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти, что увеличивает скорость поиска записи. Поскольку ключи отсортированы, можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами разреженный индекс указывает на наименьший ключ в каждом блоке.

Отрывок, характеризующий Индекс (базы данных)

Князь Андрей стал возражать и доказывать свой план, который мог быть одинаково хорош с планом Вейротера, но имел тот недостаток, что план Вейротера уже был одобрен. Как только князь Андрей стал доказывать невыгоды того и выгоды своего, князь Долгоруков перестал его слушать и рассеянно смотрел не на карту, а на лицо князя Андрея.
– Впрочем, у Кутузова будет нынче военный совет: вы там можете всё это высказать, – сказал Долгоруков.
– Я это и сделаю, – сказал князь Андрей, отходя от карты.
– И о чем вы заботитесь, господа? – сказал Билибин, до сих пор с веселой улыбкой слушавший их разговор и теперь, видимо, собираясь пошутить. – Будет ли завтра победа или поражение, слава русского оружия застрахована. Кроме вашего Кутузова, нет ни одного русского начальника колонн. Начальники: Неrr general Wimpfen, le comte de Langeron, le prince de Lichtenstein, le prince de Hohenloe et enfin Prsch… prsch… et ainsi de suite, comme tous les noms polonais. [Вимпфен, граф Ланжерон, князь Лихтенштейн, Гогенлое и еще Пришпршипрш, как все польские имена.]
– Taisez vous, mauvaise langue, [Удержите ваше злоязычие.] – сказал Долгоруков. – Неправда, теперь уже два русских: Милорадович и Дохтуров, и был бы 3 й, граф Аракчеев, но у него нервы слабы.
– Однако Михаил Иларионович, я думаю, вышел, – сказал князь Андрей. – Желаю счастия и успеха, господа, – прибавил он и вышел, пожав руки Долгорукову и Бибилину.
Возвращаясь домой, князь Андрей не мог удержаться, чтобы не спросить молчаливо сидевшего подле него Кутузова, о том, что он думает о завтрашнем сражении?
Кутузов строго посмотрел на своего адъютанта и, помолчав, ответил:
– Я думаю, что сражение будет проиграно, и я так сказал графу Толстому и просил его передать это государю. Что же, ты думаешь, он мне ответил? Eh, mon cher general, je me mele de riz et des et cotelettes, melez vous des affaires de la guerre. [И, любезный генерал! Я занят рисом и котлетами, а вы занимайтесь военными делами.] Да… Вот что мне отвечали!


В 10 м часу вечера Вейротер с своими планами переехал на квартиру Кутузова, где и был назначен военный совет. Все начальники колонн были потребованы к главнокомандующему, и, за исключением князя Багратиона, который отказался приехать, все явились к назначенному часу.
Вейротер, бывший полным распорядителем предполагаемого сражения, представлял своею оживленностью и торопливостью резкую противоположность с недовольным и сонным Кутузовым, неохотно игравшим роль председателя и руководителя военного совета. Вейротер, очевидно, чувствовал себя во главе.движения, которое стало уже неудержимо. Он был, как запряженная лошадь, разбежавшаяся с возом под гору. Он ли вез, или его гнало, он не знал; но он несся во всю возможную быстроту, не имея времени уже обсуждать того, к чему поведет это движение. Вейротер в этот вечер был два раза для личного осмотра в цепи неприятеля и два раза у государей, русского и австрийского, для доклада и объяснений, и в своей канцелярии, где он диктовал немецкую диспозицию. Он, измученный, приехал теперь к Кутузову.
Он, видимо, так был занят, что забывал даже быть почтительным с главнокомандующим: он перебивал его, говорил быстро, неясно, не глядя в лицо собеседника, не отвечая на деланные ему вопросы, был испачкан грязью и имел вид жалкий, измученный, растерянный и вместе с тем самонадеянный и гордый.
Кутузов занимал небольшой дворянский замок около Остралиц. В большой гостиной, сделавшейся кабинетом главнокомандующего, собрались: сам Кутузов, Вейротер и члены военного совета. Они пили чай. Ожидали только князя Багратиона, чтобы приступить к военному совету. В 8 м часу приехал ординарец Багратиона с известием, что князь быть не может. Князь Андрей пришел доложить о том главнокомандующему и, пользуясь прежде данным ему Кутузовым позволением присутствовать при совете, остался в комнате.
– Так как князь Багратион не будет, то мы можем начинать, – сказал Вейротер, поспешно вставая с своего места и приближаясь к столу, на котором была разложена огромная карта окрестностей Брюнна.
Кутузов в расстегнутом мундире, из которого, как бы освободившись, выплыла на воротник его жирная шея, сидел в вольтеровском кресле, положив симметрично пухлые старческие руки на подлокотники, и почти спал. На звук голоса Вейротера он с усилием открыл единственный глаз.
– Да, да, пожалуйста, а то поздно, – проговорил он и, кивнув головой, опустил ее и опять закрыл глаза.
Ежели первое время члены совета думали, что Кутузов притворялся спящим, то звуки, которые он издавал носом во время последующего чтения, доказывали, что в эту минуту для главнокомандующего дело шло о гораздо важнейшем, чем о желании выказать свое презрение к диспозиции или к чему бы то ни было: дело шло для него о неудержимом удовлетворении человеческой потребности – .сна. Он действительно спал. Вейротер с движением человека, слишком занятого для того, чтобы терять хоть одну минуту времени, взглянул на Кутузова и, убедившись, что он спит, взял бумагу и громким однообразным тоном начал читать диспозицию будущего сражения под заглавием, которое он тоже прочел:
«Диспозиция к атаке неприятельской позиции позади Кобельница и Сокольница, 20 ноября 1805 года».
Диспозиция была очень сложная и трудная. В оригинальной диспозиции значилось:
Da der Feind mit seinerien linken Fluegel an die mit Wald bedeckten Berge lehnt und sich mit seinerien rechten Fluegel laengs Kobeinitz und Sokolienitz hinter die dort befindIichen Teiche zieht, wir im Gegentheil mit unserem linken Fluegel seinen rechten sehr debordiren, so ist es vortheilhaft letzteren Fluegel des Feindes zu attakiren, besondere wenn wir die Doerfer Sokolienitz und Kobelienitz im Besitze haben, wodurch wir dem Feind zugleich in die Flanke fallen und ihn auf der Flaeche zwischen Schlapanitz und dem Thuerassa Walde verfolgen koennen, indem wir dem Defileen von Schlapanitz und Bellowitz ausweichen, welche die feindliche Front decken. Zu dieserien Endzwecke ist es noethig… Die erste Kolonne Marieschirt… die zweite Kolonne Marieschirt… die dritte Kolonne Marieschirt… [Так как неприятель опирается левым крылом своим на покрытые лесом горы, а правым крылом тянется вдоль Кобельница и Сокольница позади находящихся там прудов, а мы, напротив, превосходим нашим левым крылом его правое, то выгодно нам атаковать сие последнее неприятельское крыло, особливо если мы займем деревни Сокольниц и Кобельниц, будучи поставлены в возможность нападать на фланг неприятеля и преследовать его в равнине между Шлапаницем и лесом Тюрасским, избегая вместе с тем дефилеи между Шлапаницем и Беловицем, которою прикрыт неприятельский фронт. Для этой цели необходимо… Первая колонна марширует… вторая колонна марширует… третья колонна марширует…] и т. д., читал Вейротер. Генералы, казалось, неохотно слушали трудную диспозицию. Белокурый высокий генерал Буксгевден стоял, прислонившись спиною к стене, и, остановив свои глаза на горевшей свече, казалось, не слушал и даже не хотел, чтобы думали, что он слушает. Прямо против Вейротера, устремив на него свои блестящие открытые глаза, в воинственной позе, оперев руки с вытянутыми наружу локтями на колени, сидел румяный Милорадович с приподнятыми усами и плечами. Он упорно молчал, глядя в лицо Вейротера, и спускал с него глаза только в то время, когда австрийский начальник штаба замолкал. В это время Милорадович значительно оглядывался на других генералов. Но по значению этого значительного взгляда нельзя было понять, был ли он согласен или несогласен, доволен или недоволен диспозицией. Ближе всех к Вейротеру сидел граф Ланжерон и с тонкой улыбкой южного французского лица, не покидавшей его во всё время чтения, глядел на свои тонкие пальцы, быстро перевертывавшие за углы золотую табакерку с портретом. В середине одного из длиннейших периодов он остановил вращательное движение табакерки, поднял голову и с неприятною учтивостью на самых концах тонких губ перебил Вейротера и хотел сказать что то; но австрийский генерал, не прерывая чтения, сердито нахмурился и замахал локтями, как бы говоря: потом, потом вы мне скажете свои мысли, теперь извольте смотреть на карту и слушать. Ланжерон поднял глаза кверху с выражением недоумения, оглянулся на Милорадовича, как бы ища объяснения, но, встретив значительный, ничего не значущий взгляд Милорадовича, грустно опустил глаза и опять принялся вертеть табакерку.