Cтраница 2
Как н в главе 13, существует значительная свобода п выборе конкретных представлений таких деревьев. Коэффициент ветвления равен h по меньшей мере, Af / 2, поэтому, как следует из леммы 1бЛ, количество ошнрованнй, необходимое для вы пои не кия любого поиска или вегдькн, по сути, постоянно. [16]
Оператор присоединения ( WITH) играет в этой программе особую роль. Если страницы и на самом деле расположены во вторичной памяти, что, разумеется, необходимо в больших базах данных, то оператор присоединения, кроме того, можно интерпретировать как запрос на пересылку указанной страницы в оперативную память. Каждое обращение к search предполагает пересылку только одной страницы в оперативную память, а всего для дерева из N элементов потребуется максимум k - lognN рекурсивных обращений. Следовательно, мы должны иметь возможность накапливать в основной памяти до k страниц. На самом же деле нам надо хранить даже более чем k страниц, поскольку включение может приводить к их разделению. Кроме того, ясно, что корневую страницу лучше всего постоянно хранить в оперативной памяти, так как е нее всякий раз начинается любой поиск. [17]
Авторские сборники с большим числом произведений, построенные по тематическим разделам или циклам. Чтобы найти одно из произведений в таком сборнике, нужно точно знать, в какой раздел или цикл оно входит, чго совсем не просто. В издании, выпущенном в серии Лит. Найти в нем конкретное стихотворение сложно. Если бы изд-во разделило содержание, как это сделало французское изд-во Гарнье ( Paris: Gamier, 1977), на зеркальное оглавление ( с заглавиями циклов и заголовками частей аппарата) и на алфавитный указатель заглавий стихотворений, любой поиск бы резко упростился. [18]