4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:40, 1 ноября 2012
, 1 ноября 2012→Операции обновления
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
== Операции обновления == | == Операции обновления == | ||
Операция вставки INSERT для (a, b)-дерева вначале ищет ключ x, который должен быть вставлен. После того, как неуспешный поиск остановится в некотором листе | Операция вставки INSERT для (a, b)-дерева вначале ищет ключ x, который должен быть вставлен. После того, как неуспешный поиск остановится в некотором листе <math>\ell \;</math>, x вставляется в набор ключей <math>\ell \;</math>. Если в результате у <math>\ell \;</math> становится более b элементов, для разрешения ситуации переполнения может применяться один из двух подходов: (1) вершина <math>\ell \;</math> может быть расщеплена по среднему ключу на две вершины, каждая из которых содержит не менее a ключей, либо (2) вершина <math>\ell \;</math> может передать некоторые ключи левой или правой вершине-«сестре» (если у вершины-«сестры» достаточно места для принятия новых ключей). В первом случае новый элемент маршрутизации, разделяющий ключи в двух новых поддеревьях предка <math>\ell \;</math> – <math>\mu \;</math> – должен быть вставлен в набор ключей <math>\mu \;</math>; во втором случае необходимо обновить элемент маршрутизации в <math>\mu \;</math>, отделяющий ключи в поддереве, корнем которого является <math>\ell \;</math>, от ключей, относящихся к соответствующей вершине-«сестре» <math>\ell \;</math>. Если вершина <math>\ell \;</math> была расщеплена, вершину <math>\mu \;</math> необходимо проверить на предмет потенциального переполнения из-за вставки нового элемента маршрутизации; и это расщепление может продолжаться вверх, вплоть до корня. | ||
Операция удаления DELETE также вначале определяет ключ x, подлежащий удалению. Если (в нелистовом дереве) x располагается во внутренней вершине, то x заменяется самым большим ключом левого поддерева x (или самым маленьким ключом правого поддерева x), который располагался в листе и теперь удаляется оттуда. В листовом дереве ключи удаляются только из листьев (это удаление не влияет на корректность элемента маршрутизации более высоких уровней). В любом случае операция DELETE может привести к тому, что вершина-лист <math>\ell \;</math> будет содержать меньше a элементов. Для разрешения ситуации нехватки также применяются два подхода: (1) вершина <math>\ell \;</math> сливается с вершиной-«сестрой» слева или справа от нее; (2) ключи из левой или правой вершины-«сестры» перемещаются в <math>\ell \;</math> (если это не приведет к нехватке ключей в этой вершине). Обе стратегии обработки нехватки требуют обновления информации о маршрутизации, хранящейся в вершине-предке <math>\ell \;</math>, которая в случае слияния сама может испытать нехватку ключей. Как и при обработке переполнения, этот процесс может продолжаться вплоть до корня дерева. | |||
Заметим, что корень дерева может быть расщеплен в результате операции вставки INSERT, а также может исчезнуть, если два его единственных потомка сливаются, образуя новый корень. Это значит, что B-деревья растут и сжимаются в своей верхней части, в силу чего все листья гарантированно остаются на одном и том же уровне дерева (свойство 1 определения 1). | Заметим, что корень дерева может быть расщеплен в результате операции вставки INSERT, а также может исчезнуть, если два его единственных потомка сливаются, образуя новый корень. Это значит, что B-деревья растут и сжимаются в своей верхней части, в силу чего все листья гарантированно остаются на одном и том же уровне дерева (свойство 1 определения 1). | ||