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

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

В информатике индекс может быть:

  1. Целое число, которое идентифицирует элемент массива
  2. Структура данных с сублинейным временем поиска

Содержание

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

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

Есть три способа, как элементы массива могут быть проиндексированы[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. В языке Си, при обращении к элементу с нулевым индексом возвращает адрес начала массива, заданного именем массива (переменная со значением адреса), так как индекс здесь обозначает смещение относительно его.

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


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

  • Ядерные измерительно-информационные технологии — Ядерные измерительно информационные технологии  российский научный журнал. Издательство: ООО Издательский Дом «Технологии». Журнал выходит с 2001 года, ежеквартально. 88 полос. тираж 500 экз. Главный редактор: Чебышов, Сергей Борисович.… …   Википедия

  • Индекс — (Index) Определение индекса, виды индексов, расчет индексов Информация об определении индекса, виды индексов, расчет индексов Содержание Содержание Определение Морса Индекс подгруппы Индекс (поисковой машины) Индекс (базы ) Ветро холодовой индекс …   Энциклопедия инвестора

  • индекс (в программировании) — суффикс — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы суффикс EN suffix …   Справочник технического переводчика

  • индекс вектора — порядковый номер вектора — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы порядковый номер вектора EN vector index …   Справочник технического переводчика

  • индекс источника — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN source index …   Справочник технического переводчика

  • индекс канала — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN channel indicator …   Справочник технического переводчика

  • индекс моды — порядок моды — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы порядок моды EN mode order …   Справочник технического переводчика

  • индекс ожидания — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN waiting count …   Справочник технического переводчика

  • индекс по стандарту DIN VDE 0470 для обеспечения безопасной эксплуатации оборудования и защиты человека — Первая цифра индекса (от 0 до 6) показывает уровень защиты от проникновения пыли. Вторая (от 0 до 8) уровень защиты от попадания воды. IP 65 означает полную защиту от проникновения пыли внутрь корпуса и защиту от направленных под любым углом… …   Справочник технического переводчика

  • индекс пропускной способности линии — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN capacity index …   Справочник технического переводчика


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»