Индексы

С идейной сточки зрения это индексы, хотя с точки зрения организации и результата на полноценные индексы это конечно не тянет.
Про индексы тут:
https://moodle.vsu.ru/mod/book/view.php?id=12516&chapterid=216

Конкретно про B-деревья тут:
https://moodle.vsu.ru/mod/book/view.php?id=12516&chapterid=217

Индекс это некий инструмент позволяющий быстро что-то искать в обычно очень большом объеме информации. Про DBF который просто файл в последовательно записанными строками я уже недавно писала.
Для базы со студентами из текстов по ссылкам это выглядит как такая строка: «ИвановВоронежПетровВоронежСидоровЛипецкИвановаМоскваПетроваМосква». Т.е всё, что может сделать компьютер это дать программисту такую строку и уже ему надо будет как-то найти всех, кто например из Москвы. Строка, естественно, очень длинная, а чтобы найти всех надо посмотреть весь(!) список информации всё по той же причине: Данные тут не отсортированы по городу, они обычно вообще не отсортированы. Их вводили в той последовательности в какая на стол клались бумажки.

Чтобы хоть как-то ускорить процесс и не перерывать тысячи записей при каждой операции были придуманы индексы. Раньше они хранились в отдельных файлах с расширением например NTX. При записи информации не только добавлялась строка в хвост DBF файла но и менялось содержимое NTX файла, чтобы можно было быстро находить информацию. NTX файл меньше потому, что в нём хранится только ключ поиска. В данном примере это город, что меньше, чем город и фамилия.
Первое что там есть это все записи, отсортированные в порядке ключа, т.е записаны ключ (город) и смещение в DBF файле, т.е на сколько байт от начала надо перепрыгнуть чтобы найти нужную строку.
Но этого мало для поиска. Можно добраться до города Москвы, перерыв половину файла и быть уверенным что больше информации по Москве нету. Но всё равно слишком много информации надо просмотреть.
Потому полноценный индекс это «дерево», в котором за несколько «прыжков» можно проникнуть на глубину на который лежит ранее описанный отсортированный список. Здесь:

… до любой информации можно добраться за два прыжка по ссылкам на информацию. Если данных больше, что возрастает глубина, но не сильно. Насколько понимаю глубина N требуется для работы с 3 в степени N записями:

Если в базе 60 тысяч записей то глубина дерева индексного файла 10 и что угодно можно найти за 10 переходов.
Пусть на картинке выше нужен Омск. В корне Липецк, Ростов, Хабаровск. «О» по алфавиту больше чем «Л», но меньше чем «Р», значит идти надо по ссылке «Ростов». Там Норильск, Оренбург, Ростов. Начальная буква «О» даёт следующий переход по ветке Оренбург. А это уже последний уровень («листья дерева») т.е тот самый список ссылок на информацию, отсортированный в порядке возрастания города. Достаточно сравнить слово «Омск» с темя вариантами (Омск, Орёл, Оренбург). Если где-то есть равенство искомого и записанного, что информация найдена.
У меня информация тоже записывается сразу в два места (блог и ссылка на информацию). У меня есть несколько индексов позволяющих найти информацию (темы: дом, программировании, электричество и т.д). Точно также таблица со студентами может иметь несколько индексов. Не только о городу но и по факультету например.
Но мои «индексы» вытаскивают вовсе не всю информацию из блога а только некоторые записи, которые можно привязать к теме. Всё остальное надо искать читая подряд. С другой стороны если в базе нет нужного индекса, то и тут придётся читать подряд все записи.  И списки у меня могут быть довольно длинные а не три строки как в B-дереве NTX файла. Так что это намного быстрее чем перерывать всю информацию, но всё равно вовсе не тот уровень который принят в базах данных.
Но это именно индексы и по идее и по назначению.