как сделать из слона муху

ФЛЕНОВ МИХАИЛ AKA HORRIFIC

Спецвыпуск: Хакер, номер #071, стр. 071-048-4

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

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

[деревья.]

Индексы – очень мощное средство для экономии памяти и упрощения сортировки. Но для поиска данных все равно приходится сканировать всю таблицу, пока мы не найдем необходимую запись. Если искомый текст начинается на букву «А», то мы найдем его быстро, ведь он будет находиться в самом начале. Но если искомая строка начинается на «Я», то нам придется сканировать все данные до конца и экономия скорости будет небольшой. Да, мы все еще экономим память, так как загружаем в оперативку только индексную таблицу, а не все данные, но скорость не высокая. А если построить индекс в виде дерева, то сэкономим и место, и время.

Индексы в виде деревьев очень часто используются в базах данных, в том числе и в MS SQL Server. Так что понимание пригодится не только программистам (для реализации в собственных проектах), но и администраторам, - для лучшего понимания внутренностей баз данных.

Индекс не зря называют деревом, потому что все данные в нем располагаются именно в таком виде. Рассмотрим, как выглядит дерево в памяти, и ты сразу увидишь все преимущества и недостатки.

[прогулка по дереву.]

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

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

Ощутил преимущества древовидного индекса? Если нет, то вот они:

1 ДЛЯ ПОИСКА ДАЖЕ САМОЙ ПОСЛЕДНЕЙ ЗАПИСИ В НАБОРЕ ДАННЫХ НЕ НУЖНО ПРОСМАТРИВАТЬ АБСОЛЮТНО ВСЕ ИНДЕКСНЫЕ БЛОКИ. ВПОЛНЕ ВОЗМОЖНО, ЧТО ДОСТАТОЧНО БУДЕТ ПРОСМОТРЕТЬ ТОЛЬКО ТРИ ИЛИ ЧЕТЫРЕ.