B-дерево | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | Дерево (структура данных) | ||||||||||||||||||||
Изобретено | 1970 | ||||||||||||||||||||
Изобретено | Рудольфом Байером, Эдвардом М. МакКрайтом | ||||||||||||||||||||
Сложность времени в нотации большого O | |||||||||||||||||||||
|
В информатике B-tree представляет собой самобалансирующуюся древовидную структуру данных, которая поддерживает отсортированные данные и разрешает поиск, последовательный доступ, вставку и удаление в логарифмическом времени. B-дерево обобщает двоичное дерево поиска , позволяя использовать узлы с более чем двумя дочерними элементами. В отличие от других самобалансирующихся двоичных деревьев поиска, B-дерево хорошо подходит для систем хранения, которые читают и записывают относительно большие блоки данных, такие как диски. Он обычно используется в базах данных и файловых систем.
B-деревья были изобретены Рудольфом Байером и Эдвард МакКрейт во время работы в Boeing Research Labs, для цели эффективного управления страницей индекс для больших файлов с произвольным доступом. Основное предположение заключено в том, что индексы могут быть настолько объемными, что в основную память поместиться лишь небольшие фрагменты дерева. Статья Байера и МакКрайта «Организация и поддержка упорядоченных индексов» была впервые распространена в июле 1970 года и позже опубликована в Acta Informatica.
Байер и МакКрайт никогда не объясняли, что означает буква B: Boeing, сбалансированный, широкие, пушистые и байеровские. МакКрайт сказал, что «чем больше вы думаете о том, что означает B в B-деревьях, тем лучше вы понимаете B-деревья».
Согласно определению, которое установлено, B-дерево имеет дереве, которое имеет удовлетворяет следующим свойствам:
Ключи каждого внутреннего как значения разделения, разделяющие его поддеревья. Например, если внутренний узел имеет 3 дочерних узла (или поддеревья), тогда он должен иметь 2 ключа: 1 и 2. Все значения в крайнем левом поддереве будут меньше 1, все значения в среднем поддереве будут между 1 и 2, и все значения в крайнее правое поддерево будет больше, чем 2.
B-дерево Deep n + 1 может содержать примерно в U раз больше элементов, чем B-дерево Deep n, но стоимость операций поиска, вставки и удаления растет вместе с глубина дерева. Как и в случае с любым сбалансированным деревом, стоимость растет намного медленнее, чем количество элементов.
Некоторые сбалансированные деревья хранят значения только в конечных узлах и используют разные типы узлов для конечных узлов и внутренних узлов. B-деревья сохраняют значения в каждом узле дерева, кроме конечных узлов.
Литература по B-деревьям неоднородна по своей терминологии.
Байер и МакКрайт (1972), Комер (1979) и другие определяют порядок B-дерева как минимальное количество ключей в некорневом узле. указывает, что терминология неоднозначна количество ключей. B-дерево порядка 3 может содержать максимум 6 ключей или максимум 7 ключей. Knuth (1998) избегает проблемы, определяя порядок как максимальное количество дочерних элементов (которое на единицу больше количества ключей).
Термин лист тоже непоследовательно. Байер и МакКт (1972) считали ниже конечный уровень самым низким уровнем ключей, но Кнут считал конечный уровень на один уровень самых низких ключей. Есть много возможностей реализации. В некоторых конструкциях листья могут содержать всю запись данных; в других конструкциях листья могут содержать только указатели на запись данных. Этот выбор не является фундаментальным для идеи B-дерева.
Для простоты большинства предполагают, что существует фиксированное количество ключей, которые помещаются в узел. Основное предположение состоит в том, что размер ключа фиксирован, а размер узла фиксирован. На практике установка редакции выпуска.
В-деревья, внутренние (нелистовые ) узлы могут иметь переменное количество дочерних узлов в некотором определенном определенном диапазоне. Когда данные вставляются или удаляются из узла, его количество дочерних узлов изменяется., чтобы поддерживать предопределенный диапазон, внутренние узлы могут быть объединены или разделены. -деревья не нуждаются в повторной балансировке так часто, как другие самобалансирующиеся деревья поиска, но могут сокращать некоторое пространство, поскольку узлы заполнены не полностью, поскольку нижняя и верхняя границы количества дочерних узлов обычно фиксированы для конкретной реализации., например, в 2–3 (иногда называемый 2–3 B-tree ), каждый внутренний узел может иметь только 2 или 3 дочерних узла.
Каждый внутренний узел B-дерева содержит несколько ключей. Ключи действовать как ценности разделения, которые делит свои поддеревья. Например, если внутренний узел имеет 3 дочерних узла (или поддеревья), тогда он должен иметь 2 ключа: и . Все значения в крайнем левом поддереве будут меньше , все значения в среднем поддереве будут между и , и все значения в крайнем правом поддереве будут больше, чем .
Обычно количество ключей выбирается в диапазоне от до , где - минимальное количество ключей, а - минимальное градус или коэффициент ветвления дерево. На практике ключи занимают больше всего места в узле. Коэффициент 2 гарантирует, что узлы можно разделить или объединить. Если внутренний узел имеет ключей, то добавление этого ключа к узлу может быть выполнено путем разделения гипотетического ключевой узел на два ключевых узла и перемещение ключа, который был бы посередине, на родительский узел. Каждый разделенный узел имеет необходимое минимальное количество ключей. Аналогичным образом, если внутренний узел и его соседние ключи , то ключ может быть удален из внутреннего узла путем объединения его своим соседом. Удаление ключа приведет к тому, что внутренний узел будет иметь ключи ; присоединение к соседу добавит ключей плюс еще один ключ, перенесенный от родителя соседа. Результатом является полностью полный узел из ключей.
Количество ветвей (или дочерних узлов) от узла будет на единицу больше, чем количество ключей, хранящихся в узле. В 2-3 B-дереве внутренние узлы будут либо один ключ (с двумя дочерними узлами), либо два ключа (с тремя дочерними узлами). B-дерево иногда описывается регулируемым —или просто с наивысшим порядком ветвления, .
B-дерево поддерживаемым после вставки путем разделения узла, который может быть переполнен, из ключей, на два -клавиш и сестер и вставив ключ среднего значения в родитель. Глубина увеличивается только тогда, когда корень раскалывается, сохраняя равновесие. Точно так же Б-дерево удерживается управляемым после удаления путем слияния или перераспределения ключей между братьями и сестрами, чтобы поддерживать минимум -key для некорневых узлов. Слияние уменьшает количество ключей в родительском элементе, что может вынудить его объединить или перераспределить ключи со своими братьями и сестрами и так далее. Единственное изменение глубины происходит, когда корень имеет два дочерних элемента: и (временно) ключей, и в этом случае два родственных элемента и родительский элемент объединяются, уменьшая глубину на единицу.
Эта глубина увеличивается по мере добавления элементов к дереву, но увеличение общего объема происходит нечасто и приводит к тому, что все конечные узлы становятся еще на один узел дальше от корня.
B-деревья имеют существенные преимущества по сравнению с альтернативными реализациями, когда время доступа к данным узла значительно превышает время, затрачиваемое на обработку этих данных, потому что тогда стоимость доступа к узлу может быть обеспечена за несколько операций в пределах узла. Обычно это происходит, когда данные узла находятся в вторичной памяти, например, в дисках. При максимальном увеличении количества ключей в каждом внутреннем узле высота дерева уменьшается, а количество дорогостоящих обращений к узлу уменьшается. К тому же ребалансировка дерева происходит реже. Максимальное количество дочерних узлов зависит от информации, которая должна храниться для каждого дочернего узла, и от полного размера дискового блока или аналогичного размера во вторичной памяти. Хотя 2-3 B-дерева легче объяснить, используют вторичные хранилища, требующие большого количества дочерних узлов для производительности производительности.
Термин B-дерево может относиться к конкретному проекту или к общему классу проектов. B-дерево хранит ключи в своих внутренних узлах, но не должно хранить эти ключи в своих внутренних узлах. Общий класс включает такие разновидности, как B + дерево и B-дерево.
Обычно алгоритмы сортировки и определения характеристик операций сравнения, которые должны производиться с использованием нотации заказа. Бинарный поиск в отсортированной таблице с характеристиками, например, может быть выполнен примерно за журнал 2 N ⌉ сравнений. Если бы в таблице было 1000000 записей, то можно было бы найти конкретную запись максимально 20 сравнениями: ⌈ log 2 (1000000) ⌉ = 20.
Большие базы данных исторически хранились на диске диски. Время чтения записи на диске намного больше времени, для сравнения ключей, когда запись становится доступной. Время чтения записи с диска включает в себя время поиска и задержку вращения. Время поиска может составлять от 0 до 20 или более миллисекунд, а задержка вращения составляет в среднем около половины периода. Для привода 7200 об / мин период вращения составляет 8,33 миллисекунды. Для такого привода, как Seagate ST3500320NS, время поиска от трека к треку составляет 0,8 миллисекунды, а среднее время поиска чтения составляет 8,5 миллисекунды. Для простоты предположим, что чтение с диска занимает около 10 миллисекунд.
Тогда, наивно, время, чтобы найти одну запись из миллиона, потребует 20 чтений с диска умножить на 10 миллисекунд на чтение с диска, что составляет 0,2 секунды.
Время будет не таким уж плохим, потому что отдельные записи сгруппированы в диск блок . Блок диска может составлять 16 килобайт. Если каждая запись имеет размер 160 байтов, то в каждом блоке может храниться 100 записей. Вышеуказанное время чтения с диска было фактически всего блока. Как только головка диска находится в нужном положении, один или несколько блоков диска могут быть прочитаны с небольшой задержкой. При 100х характеристиках на блок последние 6 или около того сравнений не требуют чтения с диска - все выполнение выполняются в пределах последнего прочитанного блока диска.
Для дальнейшего ускорения поиска ускорить первые 13–14 сравнений (каждое из которых требует доступа к диску).
Значительное улучшение может быть достигнуто с помощью индекс. В приведенном выше примере начальное чтение с диска сузило диапазон поиска в два раза. Это можно улучшить, создаваемый вспомогательный индекс, первый запись в каждом блоке диска (иногда называемый разреженным индексом ). Этот вспомогательный индекс будет составлять 1% от размера исходной базы данных, но его можно искать быстрее. Поиск записи во вспомогательном индексе укажет нам, какой блок искать в основной базе данных; после поиска по вспомогательному индексу нам пришлось бы искать только в этом одном блоке базы данных - за счет еще одного чтения с диска. Индекс будет содержать 10 000 записей, поэтому потребуется не более 14 сравнений. Как и в основной базе данных, последние шесть или около того сравнений во вспомогательном индексе будут на одном и том же блоке диска. Индекс можно было найти примерно за восемь чтений с диска, а к желаемой записи можно было получить доступ за 9 чтений с диска.
Уловку создания вспомогательного индекса можно повторить для создания вспомогательного индекса к вспомогательному индексу. Это сделало бы индекс aux-aux, который потребовал бы всего 100 записей и поместился бы в один дисковый блок.
Вместо того, чтобы читать 14 блоков диска, чтобы найти нужную запись, нам нужно прочитать только 3 блока. Эта блокировка является основной идеей создания B-дерева, где дисковые блоки заполняют иерархию уровней, составляющих индекс. Чтение и поиск первого (и единственного) блока индекса aux-aux, который является корнем дерева, идентифицирует соответствующий блок в aux-index на уровне ниже. Чтение и поиск этого блока вспомогательного индекса определяет соответствующий блок для чтения, пока последний уровень, известный как конечный уровень, не идентифицирует запись в основной базе данных. Вместо 150 миллисекунд нам нужно всего 30 миллисекунд, чтобы получить запись.
Вспомогательные индексы превратили проблему поиска из двоичного поиска, требующего примерно log 2 N операций чтения с диска, до одного, требующего только журнала b N операций чтения с диска, где b - это коэффициент блокировки (количество записей в блоке: b = 100 записей в блоке в нашем примере; журнал 100 1000000 = 3 чтения).
На практике, если основная база данных часто просматривается, вспомогательный индекс и большая часть вспомогательного индекса могут находиться в дисковом кэше, поэтому они не будут вызывать чтение с диска.
Если база данных не изменяется, то компиляция индекса выполняется просто, и индекс никогда не нужно изменять. Если есть изменения, то управление базой данных и ее индексом усложняется.
Удалить записи из базы данных относительно просто. Индекс может оставаться прежним, а запись можно просто пометить как удаленную. База данных остается в отсортированном порядке. При большом количестве удалений поиск и хранение становятся менее эффективными.
Вставки в отсортированный последовательный файл могут быть очень медленными, поскольку необходимо освободить место для вставляемой записи. Чтобы вставить запись перед первой, необходимо сдвинуть все записи на одну вниз. Такая операция слишком дорога, чтобы быть практичной. Одно из решений - оставить несколько пробелов. Вместо того, чтобы плотно упаковывать все записи в блок, в блоке может быть некоторое свободное пространство для последующих вставок. Эти пробелы будут отмечены, как если бы они были «удаленными» записями.
И вставки, и удаления выполняются быстро, пока в блоке есть место. Если вставка не помещается в блок, то необходимо найти свободное место на каком-то соседнем блоке и скорректировать вспомогательные индексы. Есть надежда, что поблизости достаточно места, так что не нужно реорганизовывать множество блоков. В качестве альтернативы могут использоваться некоторые дисковые блоки, не расположенные по порядку.
B-дерево использует все идеи, описанные выше. В частности, B-дерево:
Кроме того, B-дерево минимизирует потери, гарантируя, что внутренние узлы заполнены как минимум наполовину. B-дерево может обрабатывать произвольное количество вставок и удалений.
Пусть h ≥ –1 будет высотой классического B-дерева (см. Дерево (структура данных) § Терминология для дерева определение высоты). Пусть n ≥ 0 - количество элементов в дереве. Пусть m - максимальное количество детей, которое может иметь узел. Каждый узел может иметь не более m − 1 ключей.
Можно показать (например, по индукции), что B-дерево высоты h со всеми полностью заполненными узлами имеет n = m – 1 элементов. Следовательно, оптимальная высота (т.е. минимальная высота) B-дерева равна:
Пусть будет минимальным количеством дочерних элементов, которые может иметь внутренний (не корневой) узел. иметь. Для обычного B-дерева
Comer (1979) и Cormen et al. (2001) дают наихудшую высоту (максимальную высоту) B-дерева как
Поиск аналогичен поиску в двоичном дереве поиска. Начиная с корня, дерево рекурсивно просматривается сверху вниз. На каждом уровне поиск уменьшает свое поле зрения до дочернего указателя (поддерева), диапазон которого включает значение поиска. Диапазон поддерева определяется значениями или ключами, содержащимися в его родительском узле. Эти предельные значения также известны как значения разделения.
Двоичный поиск обычно (но не обязательно) используется в узлах для поиска значений разделения и интересующего дочернего дерева.
Все вставки начинаются с листового узла. Чтобы вставить новый элемент, выполните поиск в дереве, чтобы найти листовой узел, в который следует добавить новый элемент. Вставьте новый элемент в этот узел, выполнив следующие действия:
Если разделение идет полностью до корня, создается новый корень с одним значением разделителя и двумя дочерними элементами, поэтому нижняя граница размера внутренних узлов не применяется к корню. Максимальное количество элементов на узел - U-1. Когда узел разделяется, один элемент перемещается к родительскому, но добавляется один элемент. Итак, должно быть возможно разделить максимальное количество элементов U − 1 на два допустимых узла. Если это число нечетное, то U = 2L и один из новых узлов содержит (U − 2) / 2 = L − 1 элементов и, следовательно, является допустимым узлом, а другой содержит еще один элемент, и, следовательно, он является допустимым. слишком. Если U − 1 четно, то U = 2L − 1, поэтому в узле 2L − 2 элемента. Половина этого числа составляет L − 1, что является минимальным количеством элементов, разрешенных на узел.
Альтернативный алгоритм поддерживает одиночный проход вниз по дереву от корня до узла, где будет происходить вставка, с упреждающим разделением любых полных узлов, встречающихся на пути. Это предотвращает необходимость вызова родительских узлов в память, что может быть дорогостоящим, если узлы находятся во вторичной памяти. Однако, чтобы использовать этот алгоритм, мы должны иметь возможность отправить один элемент родительскому элементу и разделить оставшиеся элементы U-2 на два допустимых узла без добавления нового элемента. Для этого требуется U = 2L, а не U = 2L − 1, что объясняет, почему некоторые учебники вводят это требование при определении B-деревьев.
Есть две популярные стратегии удаления из B-дерева.
В приведенном ниже алгоритме используется первая стратегия.
При удалении элемента следует учитывать два особых случая:
Процедуры для этих случаев приведены ниже.
Каждый элемент во внутреннем узле действует как значение разделения для двух поддеревьев, поэтому нам необходимо найти замену разлуке. Обратите внимание, что самый большой элемент в левом поддереве по-прежнему меньше разделителя. Точно так же наименьший элемент в правом поддереве по-прежнему больше, чем разделитель. Оба этих элемента находятся в листовых узлах, и любой из них может быть новым разделителем для двух поддеревьев. Алгоритмно описано ниже:
Повторная балансировка начинается с листа и продолжается к корню пока дерево не будет сбалансировано. Если удаление элемента из узла привело к тому, что он стал меньше минимального размера, тогда некоторые элементы должны быть перераспределены, чтобы свести все узлы к минимуму. Обычно перераспределение включает перемещение элемента из одноуровневого узла, количество узлов которого превышает минимальное. Эта операция перераспределения называется ротацией . Если ни один из братьев и сестер не может сохранить элемент, то дефектный узел должен быть объединен с одним из братьев и сестер. Слияние приводит к тому, что родительский элемент теряет разделительный элемент, поэтому родительский элемент может стать несовершенным и потребовать повторной балансировки. Слияние и ребалансировка могут продолжаться вплоть до корня. Поскольку минимальное количество элементов не применяется к корню, сделать корень единственным дефектным узлом не проблема. Алгоритм перебалансировки дерева следующий:
Хотя недавно загруженные базы данных, как правило, имеют хорошее последовательное поведение, это поведение становится все труднее поддерживать по мере роста базы данных, что приводит к более случайному Проблемы ввода-вывода и производительности.
Распространенный частный случай - добавление большого количества предварительно отсортированных данных в изначально пустое B-дерево. Хотя вполне возможно просто выполнить серию последовательных вставок, вставка отсортированных данных приводит к дереву, почти полностью состоящему из наполовину заполненных узлов. Вместо этого можно использовать специальный алгоритм «массовой загрузки» для создания более эффективного дерева с более высоким коэффициентом ветвления.
Когда входные данные отсортированы, все вставки происходят на самом правом крае дерева, и, в частности, каждый раз, когда узел разделяется, мы гарантируем, что больше не будет вставок в левой половине. При массовой загрузке мы пользуемся этим преимуществом, и вместо того, чтобы равномерно разделять переполненные узлы, разделяем их как можно более неравномерно: оставьте левый узел полностью заполненным и создайте правый узел с нулевыми ключами и одним дочерним (в нарушение обычного B- правила дерева).
В конце массовой загрузки дерево почти полностью состоит из полностью заполненных узлов; только крайний правый узел на каждом уровне может быть не заполнен. Поскольку эти узлы также могут быть заполнены менее чем наполовину, чтобы восстановить нормальные правила B-дерева, объедините такие узлы с их (гарантированно полными) левыми братьями и сестрами и разделите ключи, чтобы получить два узла, заполненных хотя бы наполовину. Единственный узел, у которого нет полного левого брата, - это корень, который может быть заполнен менее чем наполовину.
Помимо использования в базах данных, B-дерево (или § Варианты) также используется в файловых системах для обеспечения быстрого произвольного доступа к произвольным block in a particular file. The basic problem is turning the file block address into a disk block (or perhaps to a cylinder-head-sector ) address.
Some operating systems require the user to allocate the maximum size of the file when the file is created. The file can then be allocated as contiguous disk blocks. In that case, to convert the file block address into a disk block address, the operating system simply adds the file block address to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size.
Other operating systems allow a file to grow. The resulting disk blocks may not be contiguous, so mapping logical blocks to physical blocks is more involved.
MS-DOS, for example, used a simple File Allocation Table (FAT). The FAT has an entry for each disk block, and that entry identifies whether its block is used by a file and if so, which block (if any) is the next disk block of the same file. So, the allocation of each file is represented as a linked list in the table. In order to find the disk address of file block , the operating system (or disk utility) must sequentially follow the file's linked list in the FAT. Worse, to find a free disk block, it необходимо последовательно сканировать FAT. Для MS-DOS это не было огромным штрафом, потому что диски и файлы были небольшими, а в FAT было мало записей и относительно короткие цепочки файлов. В файловой системе FAT12 (использовавшейся на гибких дисках и ранних жестких дисках) было не более 4080 записей, и FAT обычно находилась в памяти. По мере того, как диски становились больше, архитектура FAT начала сталкиваться с недостатками. На большом диске, использующем FAT, может потребоваться выполнить чтение с диска, чтобы узнать, где на диске находится блок файла, который нужно прочитать или записать.
TOPS-20 (и, возможно, TENEX ) использовал дерево уровней от 0 до 2, которое имеет сходство с B-деревом. Дисковый блок состоял из 512 36-битных слов. Если файл помещается в блок из 512 (2) слов, то каталог файла будет указывать на этот блок физического диска. Если файл умещается в 2 слова, тогда каталог будет указывать на вспомогательный индекс; 512 слов этого индекса будут либо NULL (блок не выделяется), либо указывать на физический адрес блока. Если файл умещается в 2 слова, тогда каталог будет указывать на блок, содержащий индекс aux-aux; каждая запись будет либо NULL, либо указывать на вспомогательный индекс. Следовательно, блок физического диска для файла из 2 слов может быть расположен при двух чтениях с диска и чтении на третьем.
файловая система Apple HFS +, Microsoft NTFS, AIX (jfs2) и некоторые файловые системы Linux, такие как btrfs и Ext4, используйте B-деревья.
B-деревья используются в файловых системах HFS и Reiser4 .
DragonFly BSD в HAMMER файловая система использует модифицированное B + -дерево.
B-дерево растет медленнее с увеличением объема данных, чем линейность связанного списка. По сравнению с пропускаемым списком обе структуры имеют одинаковую производительность, но B-дерево лучше масштабируется для роста n. T-tree для систем с базой данных в основной памяти аналогично, но более компактно.
Леман и Яо показали, что всех блокировок чтения можно избежать (и, таким образом, значительно улучшить параллельный доступ), связав блоки дерева на каждом уровне вместе с указателем «следующий». Это приводит к древовидной структуре, в которой операции вставки и поиска спускаются от корня к листу. Блокировки записи требуются только при изменении блока дерева. Это максимизирует параллелизм доступа для нескольких пользователей, что является важным аспектом для баз данных и / или других методов хранения на основе B-дерева ISAM. Цена, связанная с этим улучшением, заключается в том, что пустые страницы не могут быть удалены из btree во время обычных операций. (Тем не менее, см. Различные стратегии для реализации объединения узлов и исходный код в.)
United St. Патент 5283894, выданный в 1994 году, по-видимому, показывает способ использования «метода метадоступа» для одновременного доступа и модификации дерева B + без блокировок. Этот метод обращается к дереву «вверх» как для поиска, так и для обновлений с помощью дополнительных индексов в памяти, которые указывают на блоки на каждом уровне в кеш-памяти блоков. Никакой реорганизации для удалений не требуется, и в каждом блоке нет указателей «следующий», как в Lehman и Yao.
Правила B-деревья аналогичны по структуре красно-черным деревьям, могут использовать параллельные алгоритмы для красно-черных деревьев к B- деревьям.
На Викискладе есть носители, связанные с B-деревьями. |
Массовая загрузка