Лекция №26

Название лекции: Анализ временных характеристик над В–деревьями.

План:

1. Анализ временных характеристик над В–деревьями.

2. Файлы с плотным индексом.

3. Преимущество плотного индекса.

4. Файлы с записями переменной длины. Основные стратегии решения и методы реализации.

5. Структуры данных для организации поиска по не ключевым полям:

5.1. Вторичные индексы (инвертированные файлы);

5.2. Поиск по частичному соответствию.

1. Анализ временных характеристик над В–деревьями.

Рассмотрим файл с n записями, организованный в виде В–дерева с параметрами d и e, где d – параметр файла, e – параметр индекса. Оценка листьев: предположим, что все блоки заполнены по минимуму. Количество записей в блоке 2е-1, количество в главном файле n/е листьев, количество блоков в индексе n/dе, на следующем уровне n/d²е. Если путь от корня к листу i, то ; но корень только один ; ухудшим эту оценку ;

чтобы выполнить поиск достаточно i операции чтения. Для операции включения, удаления или модификации необходимо написать лишь один блок лист, содержащий запись. В сложных случаях требуется еще не более i операции чтения и записи. Такой анализ сложен. Показано что даже при d=2 и е=2 среднее число дополнительных операций (сверх i чтений и одной записи) представляет собой правильную дробь, то есть число меньше единице и ей можно пренебречь. Таким образом, общая оценка числа доступов: 2+log_d (n/e)

Пример: если n=10⁶; е=5 и d=50 ожидаемое число операций чтение–запись: 2+log₅₀200000≤6 это хуже, чем у хеширования (около 3-х), но лучше, чем у одноуровневых индексов.

Дата добавления: 2014-01-05