algorithm - 二叉搜索树和m-way树的区别

Question

请解释二叉搜索树和m-way树的区别？

Answer 1

m 向树是一种树结构，具有 m 个值和 m + 1 个链接。

二叉树是 m-way 树的一种特殊情况，m 等于 1，这意味着每个节点只有一个值和两个链接(您可以向下移动到左侧或右侧链接).这是一个二叉树的示例，显示了这一点:

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

m 路树的每个节点可以有多个值，但理论仍然相同。您可以根据值选择要向下移动到的链接，并且有 m + 1 种可能的选择。 m 路树(其中 m 为 2)可能如下所示:

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

这些 m-way 树通常用于可以在一个有效 block 中容纳多个值的情况。高效是指可以高效读取和写入的数据，例如磁盘 block 、扇区、簇或柱面，具体取决于您的存储子系统的运行方式。

例如，假设:

• 一个磁盘 block 是512字节；
• 树中的值占用 122 个字节；和
• 链接占用4个字节。

在这种情况下，您可以将 4 个值放入一个磁盘 block 中，计算如下:

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

虽然存在一些浪费(在本例中为四个字节)，但这样做的好处是可以在每个可高效检索的 block 中存储整数个值。