Классика баз данных - статьи

       

В этом случае нам надо


В этом случае нам надо добавить дополнительную вершину с префиксом key, дочернюю по отношению к последней вершине пути.
  • key и rest — суть непустые строки. В этом случае последняя вершина xn разбивается на три: одну с префиксом common, с двумя исходящими из неё — xn, префиксом которой становится rest, и final-вершину с префиксом key.

    Основной момент, который связан с разделением на блоки, заключается в том, что в случае 4 и 5 если ветка, в которую мы производим добавление, имеет дочерние ветки, мы создаём новую вершину с key в новой ветке. Для этого мы находим среди дочерних веток ту, на странице которой осталось больше всего места. Это самая дорогая из всех приведённых операций, т.к. требует в худшем случае чтение такого количества страниц, которое равно количеству различных возможных дочерних веток. На практике это неприемлемо. Поэтому в нашей реализации мы ограничеваем количество просматриваемых страниц некоторой константой D (в реализации равна 2). В случае, если среди первых просмотренных D страниц не нашлось той, в которую помещается добавляемая вершина, пытаемся расширить самую занятую из просмотренных. При таком подходе затрагивается не более D+2 страниц.


    Содержание  Назад  Вперед