Организация и функционирование компьютеров


Использование деревьев для индексирования


Дерево называется бинарным, если каждая вершина имеет не более двух подчиненных (не более двух слуг). Бинарные деревья принято задавать иначе, чем произвольные деревья. Вместо ссылок от вершины “вниз” и “вправо” структура дерева задается ссылками к первому (“левому”) и второму (“правому”) слуге данного хозяина. Если один или оба слуги отсутствуют, соответствующие ссылки равны Nil. Путь на бинарном дереве от корня до любой вершины кодируется последовательностью нулей и единиц: нуль соответствует переходу к левому слуге, а единица - к правому. Классификация с помощью бинарного дерева называется бинарной классификацией.

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

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

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


- Начало -  - Назад -  - Вперед -



Книжный магазин