Cтраница 2
На рис. 30.8 показан фрагмент индексного дерева. В основной памяти находятся буферы повторного поиска для трех уровней дерева. Просматривая буфер уровня 1, получаем из него ссылку на нужный блок набора указателей. [16]
Пусть строка л-й таблицы занимает а условных ячеек. Стратегия поиска определяется параметрами Xj и, возможно, числом п уровней дерева поиска. [17]
Один из недостатков структуры сбалансированного дерева для организации индекса заключается в том, что при поиске каждой записи нужно проходить через все уровни дерева. В этом случае невозможно использовать специальные процедуры доступа к часто используемым записям и к записям, хранящимся на устройствах с наи более быстрым доступом. [18]
Программист может использовать возможность произвольного выбора места в памяти для вспомогательного дерева, заготовив семейство адресов, по одному адресу для начала каждого уровня дерева. Эти адреса разделяют уровни дерева, Облегчая использование разделенного на части пространства памяти. Однако, что важнее, они сокращают число делений, умножений, сдвигов и других операций при сортировке. [19]
Общее число уровней дерева целей определяется сложностью системы, развитие которой планируется. Элементы самого нижнего уровня дерева обычно представляют собой цели работ выполнение которых необходимо для достижения целей всех вышележащих уровней, причем дробление этих работ на какие-либо составные части не имеет практического смысла ни при долгосрочном планировании, ни при управлении выполнением этих работ. Каждому уровню дерева целей соответствует один и тот же общий объем планируемых работ; уровни дерева целей отличаются друг от друга только степенью детализации задачи развития системы. [20]
Существует много способов размещения блоков индексного дерева. В некоторых пакетах программ управления файлами уровни дерева привязаны к секциям внешнего запоминающего устройства, таким, например, как отдельные дорожки диска. Однако, как это видно из рис. 30.4, оптимальный размер индексного блока довольно мал, поэтому на одной дорожке иногда умещается несколько уровней дерева. [21]
На рис. 24.2 и 24.4 приведены примеры простых двухуровневых файлов. В системах обработки данных двухуровневые файлы используются часто; например, для банковской системы используются записи счетов клиентов и записи о сделках клиентов. Эти записи обычно рассматриваются соответственно как главные и детальные записи и изображаются в виде двухуровневого дерева. Для любого такого файла или для любой пары уровней дерева разработчик имеет возможность выбора степени включения некоторых сегментов нижнего уровня в сегменты верхнего уровня. Обычно все сегменты нижнего уровня размещаются отдельно от сегментов верхнего уровня или же объединяются с ними. Однако при использовании графиков, показанных на рис. 24.3, можно найти компромиссное решение ( рис. 24.4), которое может оказаться лучше решения, найденного по принципу все или ничего. [22]
Найдем путь от корня В-дерева к некоторому листу, в котором будет находиться требуемая запись, если она существует. Предположим, что в некоторый момент мы достигли узла ( блока) В. To обстоятельство, что лист достигнут, нетрудно установить, если обеспечивается доступ к текущему номеру уровней дерева. [23]
Напомним, что процедура поиска дает путь от корня к блоку В. Применим процедуру включения рекурсивно с константой d вместо е для того, чтобы включить в блок индекса Р запись для блока BL правее записи для блока В. Заметим, что, если многие предки блока имеют максимальное число 2d - 1 записей, эффект включения некоторой записи в блок) В может распространиться на несколько уровней дерева. Однако затрагиваются при этом только предки В. В том случае, когда влияние включения записи достигает корня, он расщепляется и создается новый корень с двумя сыновьями. Это единственная ситуация, при которой блок индекса может иметь менее d записей. [24]
Стандартная терминология для структур типа дерева обязана своим происхождением второй форме генеалогического древа, родовой схеме. Говорят, что каждый корень является отцом корней своих поддеревьев и что последние являются братьями между собой и сыновьями своего отца. Корень же всего дерева не имеет отца. Например, на рис. 19 С имеет трех сыновей: D, Е и F; Е является отцом G; В и С - братья. Некоторые авторы используют женскую терминологию: мать, дочь, сестра вместо отец, сын, брат, но по некоторым причинам слова мужского рода предпочтительнее. В любом случае мы употребляем слова предок и потомок для обозначения родства, которое может простираться на несколько уровней дерева. [25]