Классика баз данных - статьи
На каждую первичную структуру хранения
На каждую первичную структуру хранения данных может приходиться от одного до нескольких экземпляров механизма поиска.
В-деревья состоят из узлов, связанных в иерархию так, что каждый более верхний узел связан с несколькими более нижними узлами, за исключением корневого узла, связанного только с узлами более нижнего уровня, и листовых узлов (листьев), связанных только с одним узлом более верхнего уровня. В каждом узле располагается набор атрибутов и, в случае реляционной базы, списки идентификаторов данных, в состав которых входят указанные атрибуты. Отдельный атрибут отражается только в одном из узлов дерева. Объем узла имеет переменный размер в связи с неограниченностью количества идентификаторов данных, в состав которых могут входить атрибуты, отраженные в узле.
Для локализации места расположения идентификаторов данных применяют В+-деревья, в составе которых отдельный атрибут отражается в нескольких узлах в направлении иерархической связи, ведущей к одному из листов дерева, где, кроме этого атрибута, отражается список связанных с ним идентификаторов данных [2]. В общем случае атрибут отражается в количестве узлов, равном половине от числа уровней В+-дерева.
Выбор деревьев в качестве механизмов поиска был основан на стремлении минимизировать число обращений к энергонезависимому накопителю информации, обладающему на один-два порядка меньшим быстродействием по сравнению с оперативной памятью компьютера, на котором устанавливается система управления базой данных. В связи с возможностью неограниченного роста размера каждого из узлов В-дерева все они располагаются на энергонезависимом носителе информации, вынуждая обращаться к нему на этапах как записи, так и чтения данных.
В В+-дереве информация переменного размера локализуется в листьях, которые размещаются на энергонезависимом носителе информации. Узлы, в которых отражается только заранее известное число атрибутов, могут быть размещены в оперативной памяти компьютера. На этапе записи одного атрибута количество обращений к энергонезависимому носителю информации составит половину от числа уровней дерева плюс одно обращение для записи элемента данных в реляционную таблицу, на этапе чтения поиск будет производиться только в оперативной памяти компьютера.
