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

Индекс (информационные технологии)

Содержание

Идентификатор элемента массива

Для объектов данных хранящихся в массиве, отдельные объекты выбираются индексом, который обычно является неотрицательным скалярным целым числом.

Есть три способа, как элементы массива могут быть проиндексированы [1] :

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

Массив может иметь несколько измерений, таким образом обычная практика обращаться к массиву, используя несколько индексов. Например к двумерному массиву с тремя строками и четырьмя столбцами можно было бы обратиться к элементу в 2-ом ряду и 4-ой столбце с помощью выражения: [1,3] (в языке в котором приоритет у строки) и [3,1] (в языке в котором приоритет у столбца) в случае индексом с началом с нуля. Таким образом два индекса используются для двумерных массивов, три для трехмерного массива, и n для n-мерного массива.

За деталями поддержки различных особенностей в языках программирования см. Сравнение языков программирования (массивы).

Поисковой индекс: поддержка быстрого поиска

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

Объяснение на примере

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

Однако, использование таких чисел не может быть удобным, так же, как «wikipedia.org» предпочтительнее чем тридцатидвухбитное число 3494942722 представленное в форме IP как 208.80.152.2. Наивный алгоритм был бы такой: подготовить список имен и при поиске некоторого конкретного имени, каждое имя из списка по очереди проверять, с начала до конца. В случае успешного поиска проверяется в среднем половина из них, в худшем случае проверяются все элементы, в итоге выдавая результат «не найдено»; Время работы алгоритма O(N), оно же линейное время. Так как хранилища данных нередко содержат миллионы объектов и так как поиск — достаточно частая операция, желательно изменить его работу к лучшему.

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

Аспекты применения

Индекс — любая структура данных, которая улучшает работу поиска. Есть много различных структур данных, используемых с этой целью, и фактически существенная часть предмета информатики посвящена проектированию и анализу структур данных поискового индекса. Есть сложность в выборе компромиссов при выборе дизайна поискового индекса, рассматривая такие параметры как быстродействие при поиске, размер индекса, и скорость обновления индекса. Многие дизайны индекса показывают логарифмическое (O (log(N)) время работа поиска, а в некоторых приложениях даже возможно достигнуть равномерного-O (1) быстродействия.

Все базы данных содержат технологии индексации для обеспечения быстрого поиска в данных. См. Индекс (базы данных).

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

Источник

Индекс (массив)

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

Есть три способа, как элементы массива могут быть проиндексированы целыми неотрицательными числами [1] :

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

Массив может иметь несколько измерений, таким образом обычная практика обращаться к массиву, используя несколько индексов. Например к двумерному массиву с тремя строками и четырьмя столбцами можно было бы обратиться к элементу в 2-ом ряду и 4-ой столбце с помощью выражения: [1,3] (в языке в котором приоритет у строки) и [3,1] (в языке в котором приоритет у столбца) в случае индексом с началом с нуля. Таким образом два индекса используются для двумерных массивов, три — для трехмерного массива, и n — для n-мерного массива.

Примечания

Полезное

Смотреть что такое «Индекс (массив)» в других словарях:

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

индекс — Индексом является 16 битовый адрес, используемый для доступа к объектному словарю CANopen. Для массивов и записей этот адрес расширяется 8 битовым субиндексом. [http://can cia.com/fileadmin/cia/pdfs/CANdictionary v2 ru.pdf] индекс 1. Индексный… … Справочник технического переводчика

Индекс — [index] 1. Индексный показатель [index value, index number], величина, получаемая как отношение показателей одинаковой размерности при их сопоставлении (например, за различные периоды времени, для разных территорий). Поэтому индексы … … Экономико-математический словарь

массив данных — Конструкция данных, компоненты которой идентичны по своим характеристикам и перечисляют как значения функции от фиксированного количества целочисленных аргументов. Примечание Количество аргументов определяет размерность массива. [ГОСТ 20886 85]… … Справочник технического переводчика

Индекс подобия Земле — (англ. Earth Similarity Index, ESI) индекс пригодности планеты или луны для жизни, разработанный международной группой учёных, которую составили астрономы, планетологи, биологи и химики[1][2]. ESI должен помочь ответить на вопрос,… … Википедия

Индекс обитаемости планеты — (англ. Planetary Habitability Index, PHI) индекс вероятности существования жизни на каком либо небесном теле, разработанный международной группой учёных, которую составили астрономы, планетологи, биологи и химики[1][2]. Индекс PHI… … Википедия

Индекс поисковой системы — в Интернет компонента поисковой системы; информационный массив, в котором хранятся специальным образом преобразованные текстовые составляющие всех посещенных и проиндексированных роботом веб страниц и текстовых файлов. По английски: Index См.… … Финансовый словарь

Массив (программирование) — Индексный массив (в некоторых языках программирования также таблица, ряд) именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом (в отличие от списка), доступ к которым осуществляется по индексу. Индекс… … Википедия

Массив — У этого термина существуют и другие значения, см. Массив (значения). Эту страницу предлагается переименовать в Массив (информатика). Пояснение причин и обсуждение на странице Википедия:К переименованию/4 ноября 2012. Возможно, её … Википедия

Массив Раглицы — Территория Массив Раглицы Страна РоссияРоссия … Википедия

Источник

Что такое индексы базы данных (для начинающих)?

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

Что такое индекс базы данных и зачем он нужен?

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

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

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

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

Теперь, представьте себе, что речь идет не об одной полочке, а об огромном помещении, где находятся тысячи книг.

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

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

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

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

Так вот, в данном примере, если переносить это в базу данных:

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

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

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

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

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

Так же можно заметить, что добавление индекса не требует того, чтобы сами sql-запросы были переписаны, так как последние являются лишь выражением на упрощенном языке для базы данных. Если продолжить аналогию, то это как попросить кого-то найти вам «Флора и фауна». При этом каким образом и сколько этот кто-то будет искать книгу, будет решать сам этот человек. В данном примере «найти книгу» — это sql-запрос, а этот «кто-то» это база данных.

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

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

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

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

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

Теперь поясню откуда берется логарифм. Дело в том, что дерево обычно заполняется по определенным правилам. К примеру, если у узла максимально может быть всего два дочерних узла (так называемое бинарное дерево), то обычно левый дочерний узел имеет значение меньше текущего, а правый большее значение. Поэтому если вам нужно найти, например, число 30 в дереве с рисунка чуть выше, то вам понадобится всего 4 сравнения (40 — 25 — 32 — 30). Именно из-за этой особенности поиска и берется логарифм (так как каждое сравнение сокращает количество проверяемых элементов в два раза). При этом обычно значение логарифма округляют в большую сторону.

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

Как видите, чтобы здесь найти запись с ключом «3» понадобится 4 сравнения (40 — 25 — 10 — 3), хотя всего записей 5.

Практически во всех базах данных, существует деление по уникальности:

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

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

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

Так же стоит знать, что индексы делятся по количеству входящих в них полей:

Обычные индексы — состоят из одного поля. Здесь, вероятно, все понятно. Обычный каталог страничек.

Составные индексы — строятся по нескольким полям, при этом расположение полей является важным.

Чуть подробнее про составные индексы. Рассмотрим аналогию с теми же книгами. До этого индекс строился только по названию. Теперь же представим, что книги с одинаковыми названиями часто встречаются. В такой ситуации, легко может получится, что страничка каталога будет состоять из координат сотен книг (десятки авторов и у каждого по десять копий). Бегать их всех проверять — так же немалое количество времени. Поэтому вместо того, чтобы страничка просто перечисляла все местонахождения книг, можно сделать так, чтобы странички с именами книг указывали на дополнительные каталоги, где аналогичным образом проиндексированы авторы.

Немного упрощая, поиск будет выглядит примерно так.

1. Вначале вы ищите в каталоге с именами необходимую страничку с названием.

2. Затем в этой страничке смотрите, где находится соответствующий каталог с авторами.

3. Берете этот каталог и уже в нем находите страничку, где указано месторасположение всех книг с этим автором и названием.

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

Существуют и другие моменты, но чаще всего достаточно знать хотя бы эти базовые знания.

Источник

15) Индексирование в базах данных

Что такое индексирование?

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

Из этого руководства по индексированию СУБД вы узнаете:

Типы индексации

Индексация базы данных определяется на основе ее атрибутов индексации. Два основных типа методов индексации:

Первичная индексация

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

Первичная индексация также делится на два типа.

Плотный индекс

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

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

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

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

Пример разреженного индекса

Вторичный индекс

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

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

Пример вторичной индексации

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

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

Индекс кластеризации

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

Пример:

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

Он рассматривается в одном кластере, а индексные точки указывают на кластер в целом. Здесь Department _no — неуникальный ключ.

Что такое многоуровневый индекс?

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

B-Tree Index

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

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

Преимущества индексации

Важные плюсы / преимущества индексирования:

Недостатки индексации

Важными недостатками / минусами индексации являются:

Источник

Индексация (программирование)

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

Связанные понятия

Упоминания в литературе

Связанные понятия (продолжение)

В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того.

Схе́ма — графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения данных, потока, оборудования и т. д.Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности. Правила выполнения регламентируются ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем.

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

В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры.

Источник