Шпоры по МПиПА1

24. Методы поиска во внешней памяти (В – деревья, В+ - деревья). B – деревья. Принято корневую вершину или корневой узел постоянно держать в памяти, дополнительно сокращая количество обращений n к диску на 1. Такие структуры изобретены в 1972 году и называются B-деревьями. С войства B-дерева порядка m: 1). Каждый узел имеет более m потомков. 2). Каждый узел за исключением корня и листьев имеет не менее [m/2] потомков. 3). Корневой узел, если он не является листом, имеет минимум двух потомков. 4). Все листья содержатся на одном уровне и не содержат информации. Их можно представить как указатели, равные нулю. 5). Нелистовый узел с k потомками имеет k-1 ключ. 6). Информация содержится в любом узле дерева. m=7 min=[7/2]=3 max=6 Указатель p0 указывает на узел с ключами, большими k1, но меньшими k2. Запись с ключом k1 хранится в данном узле.В отличие от остальных видов деревьев, B-деревья растут сверху вверх. Рост дерева возникает при необходимости деления корневого узла при его переполнении. При этом необходимо создать для корня родительский узел. При удалении значений необходимо предусматривать проверку заполненности вершин (по 2-му свойству B-деревьев: количество потомков >=m/2). B*- и B^+- деревья При построении дерева изначально резервируется место для каждого узла, исходя из максимального количества ключей и указателей на потомков в нём. Поэтому для устранения этого недостатка была создана новая модель деревьев, которые называются B*-деревья. Они отличаются от остальных тем что для узлов не явл. листьями и корнем кол-во потомков составляет от 2/3m до m. Недостатки: 1). Больше количество трансформаций дерева при вставке и удалении значений. При удалении для обоих типов деревьев (B- и B*-) необходимо предусмотреть проверку заполненности узлов и, если требуется, объединить соседние узлы в слое. 2). (для обоих видов деревьев) При модификации дерева необходимо перемещать записи вместе с ключами в другие вершины (узлы). Чтобы исключить эту процедуру, предложена модель B^+-деревьев, в которых вся информация хранится в листьях, а вышележащих слоях располагаются только копии ключей, используемых для ускорения поиска данных. В листьях все данные упорядочены. В таких деревьях указатель слева от ключа ведёт к значениям, меньшим, чем данный ключ, а указатель справа – к значениям, большим либо равным данному ключу.