Распределенная обработка данных. Найханова Л.В. - 68 стр.

     При этом выдерживаются следующие свойства:
            - ключ(1) <= ключ(2) <= ... <= ключ(n);
            - в странице дерева Nm находятся ключи k со значениями ключ(m) <= k
                <= ключ(m+1).
     Листовая страница обычно имеет следующую структуру:
               ключ(1) сп(1) ключ(2) сп(2) … ключ(n) сп(n) ключ(t) сп(t)
     Листовая страница обладает следующими свойствами:
                           ключ(1) < ключ(2) < ... < ключ(t);
      где сп(r) - упорядоченный список идентификаторов кортежей (tid), включающих
значение ключ(r); листовые страницы связаны одно- или двунаправленным списком.
      Поиск в B-дереве - это прохождение от корня к листу в соответствии с заданным
значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные,
то для выполнения поиска по любому значению ключа потребуется одно и то же (и
обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном
дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице
помещается n ключей, то при хранении m записей требуется дерево глубиной logn(m), где
logn вычисляет логарифм по основанию n. Если n достаточно велико (обычный случай), то
глубина дерева невелика, и производится быстрый поиск.
      Основной "изюминкой" B-деревьев является автоматическое поддержание свойства
сбалансированности. Рассмотрим, как это делается при выполнении операций занесения и
удаления записей.
      При занесение новой записи выполняется следующим образом:
      - Поиск листовой страницы. Фактически, производится обычный поиск по ключу.
         Если в B-дереве не содержится ключ с заданным значением, то будет получен
         номер страницы, в которой ему надлежит содержаться, и соответствующие
         координаты внутри страницы.
      - Помещение записи на место. Естественно, что вся работа производится в
         буферах оперативной памяти. Листовая страница, в которую требуется занести
         запись, считывается в буфер, и в нем выполняется операция вставки. Размер
         буфера должен превышать размер страницы внешней памяти.
      - Если после выполнения вставки новой записи размер используемой части буфера
         не превосходит размера страницы, то на этом выполнение операции занесения
         записи заканчивается. Буфер может быть немедленно вытолкнут во внешнюю
         память, или временно сохранен в оперативной памяти в зависимости от политики
         управления буферами.
      - Если же возникло переполнение буфера (т.е. размер его используемой части
         превосходит размер страницы), то выполняется расщепление страницы. Для
         этого запрашивается новая страница внешней памяти, используемая часть буфера
         разбивается грубо говоря пополам (так, чтобы вторая половина также начиналась
         с ключа), и вторая половина записывается во вновь выделенную страницу, а в
         старой странице модифицируется значение размера свободной памяти.
         Естественно, модифицируются ссылки по списку листовых страниц.
      Чтобы обеспечить доступ от корня дерева к заново заведенной страницы,
необходимо соответствующим образом модифицировать внутреннюю страницу,
являющуюся предком ранее существовавшей листовой страницы, т.е. вставить в нее
соответствующее значение ключа и ссылку на новую страницу. При выполнении этого
действия может снова произойти переполнение теперь уже внутренней страницы, и она
будет расщеплена на две. В результате потребуется вставить значение ключа и ссылку на
новую страницу во внутреннюю страницу-предка выше по иерархии и т.д.



68