Индекс (информационные технологии) | это... Что такое Индекс (информационные технологии)? (original) (raw)
У этого термина существуют и другие значения, см. Индекс.
В информатике индекс может быть:
- Целое число, которое идентифицирует элемент массива
- Структура данных с сублинейным временем поиска
Содержание
Идентификатор элемента массива
Для объектов данных хранящихся в массиве, отдельные объекты выбираются индексом, который обычно является неотрицательным скалярным целым числом.
Есть три способа, как элементы массива могут быть проиндексированы[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) быстродействия.
Все базы данных содержат технологии индексации для обеспечения быстрого поиска в данных. См. Индекс (базы данных).
Еще одно специфичное, но часто встречающееся приложение — в области информационного поиска, где полнотекстовое индексирование позволяет быстро идентифицировать документы, основываясь на их текстовом содержании.
См. также Индекс (поисковой машины)
Примеры поисковых индексов
- Алгоритм двоичного поиска Быстрый поиск в сортированном списке, известный также как метод «деления пополам» или дихотомии
- Хеш-таблица Создание индекса для быстрого поиска при непоследовательных ключах хранилища