Разница между бинарным деревом поиска и m-way деревом

Question

Пожалуйста, объясните разницу между бинарным деревом поиска и m-way tree?

Answer 1

M-way дерево - это древовидная структура, которая имеет m значения и m + 1 ссылки.

Бинарное дерево - это особый случай m-way дерева с m, равным единице, что означает только одно значение на узел и две ссылки (вы перемещаетесь вниз по левой или правой ссылке). Вот пример двоичного дерева, которое показывает это:

             +----+
             | 20 |
             +----+
            /      \
      +----+        +----+
      | 14 |        | 23 |
      +----+        +----+

У m-way дерева может быть более одного значения на узел, но теория все та же. Вы выбираете, к какой ссылке переходить, основываясь на значениях, и есть m + 1 возможных вариантов. Дерево m-way (где m равно 2) может выглядеть так:

              +----+----+
              | 17 | 30 |
              +----+----+
       ______/     |     \______
      /            |            \
+----+----+   +----+----+   +----+----+
| 11 | 15 |   | 19 | 28 |   | 33 | 34 |
+----+----+   +----+----+   +----+----+

Эти m-way деревья часто используются в ситуациях, когда вы можете разместить более одного значения в эффективном блоке. Под эффективностью я имею в виду тот, который можно эффективно читать и записывать, например, дисковый блок, сектор, кластер или цилиндр, в зависимости от того, как работает ваша подсистема хранения.

Например, скажем, что:

• блок диска составляет 512 байт;
• значения в вашем дереве занимают 122 байта; и
• ссылки занимают 4 байта.

В этой ситуации вы можете разместить 4 значения в блоке диска, рассчитанном следующим образом:

numvals = int ((blocksize - linksize) / (valuesize + linksize))
        = int ((   512    -     4   ) / (   122    +     4   ))
        = int (          508          /            126        )
        = int (                    4.0317                     )
        =                             4

Это дает вам четыре значения и пять ссылок на общую сумму 508 байт:

4 * 122 = 488
5 *   4 =  20
          ---
          508

Хотя есть некоторые потери (в данном случае четыре байта), это имеет преимущество в хранении целого числа значений в каждом эффективно извлекаемом блоке.

Answer 2

A дерево бинарного поиска имеет только две фиксированные ветви и поэтому намного проще в реализации. m-way деревья, такие как B-деревья обычно используются, когда дерево должно храниться на диске, а не в памяти. Примеры включают файловые системы и индексы базы данных.

Answer 3

m-way search tree - это m-way tree, в котором:

Каждый узел имеет m дочерних и m-1 ключевых полей. Ключи в каждом узле расположены в порядке возрастания. Ключи в первом я детей меньше, чем i-й ключ Ключи в последних m-i дочерних элементах больше, чем i-й ключ

Расширением дерева многостороннего поиска порядка m является B-дерево порядка m. Этот тип дерева будет использоваться, когда данные, к которым осуществляется доступ / которые хранятся, расположены на вторичных устройствах хранения, поскольку они позволяют хранить большие объемы данных в узле.

B-дерево порядка m - это дерево поиска в нескольких направлениях, в котором:

Корень имеет как минимум два поддерева, если только он не является единственным узлом в дереве. Каждый некорневой и каждый неконечный узел имеют не более m непустых дочерних элементов и по меньшей мере m / 2 непустых дочерних элементов. Количество ключей в каждом некорневом и каждом ненулевом узле на единицу меньше числа его непустых дочерних элементов. Все листья находятся на одном уровне.