二叉搜索树和m路树之间的区别

Please explain the difference between a binary search tree and m-way tree?

请解释二叉搜索树和m-way树之间的区别?

3 个解决方案

#1

An m-way tree is a tree structure that has m values and m + 1 links.

m-way树是具有m值和m + 1个链接的树结构。

A binary tree is a special case of an m-way tree with m equal to one, meaning only one value per node and two links (you either move down to the left or the right link). Here's an example of a binary tree that shows this:

二叉树是m路树的一种特殊情况,m等于1,意味着每个节点只有一个值和两个链路(向下移动到左侧或右侧链路)。这是一个显示以下内容的二叉树示例:

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

An m-way tree can have more than one value per node but the theory is still the same. You choose which link to move down to based on the values, and there's m + 1 possible choices. An m-way tree (where m is 2) may look like this:

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

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

These m-way trees are often used in situations where you can fit more than one value in an efficient block. By efficient, I mean one that can be read and written efficiently, like a disk block, sector, cluster or cylinder depending on how your storage subsystem operates.

这些m-way树通常用于可以在有效块中放入多个值的情况。有效率,我的意思是可以高效读取和写入,如磁盘块,扇区,集群或柱面,具体取决于存储子系统的运行方式。

For example, let's say that:

例如,让我们说:

a disk block is 512 bytes;

磁盘块是512字节;

the values in your tree take up 122 bytes; and

树中的值占用122个字节;和

the links take up 4 bytes.

链接占用4个字节。

In this situation, you can fit 4 values into a disk block, calculated as follows:

在这种情况下,您可以将4个值放入磁盘块中,计算方法如下:

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

That gives you four values and five links for a total of 508 bytes:

这为您提供了四个值和五个链接,总共508个字节:

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

Although there's some wastage (four bytes in this case), this has the advantage of storing an integral number of values in each efficiently-retrievable block.

尽管存在一些浪费(在这种情况下为四个字节),但这具有在每个可高效检索的块中存储整数个值的优点。

#2

A binary search tree has only two fixed branches and is therefore a lot easier to implement. m-way trees such as B-trees are generally used when the tree has to be stored on disk rather than in memory. Examples include file systems and database indexes.

二叉搜索树只有两个固定分支,因此更容易实现。当树必须存储在磁盘而不是存储器中时,通常使用诸如B树之类的m路树。示例包括文件系统和数据库索引。

#3

an m-way search tree is a m-way tree in which:

m-way搜索树是一种m-way树,其中:

Each node has m children and m-1 key fields The keys in each node are in ascending order. The keys in the first i children are smaller than the ith key The keys in the last m-i children are larger than the ith key

每个节点有m个子节点和m-1个键字段每个节点中的键按升序排列。第一个i子项中的键小于第i个键最后一个m-i子项中的键大于第i个键

An extension of a multiway search tree of order m is a B-tree of order m. This type of tree will be used when the data to be accessed/stored is located on secondary storage devices because they allow for large amounts of data to be stored in a node.

阶数m的多路搜索树的扩展是阶数为m的B树。当要访问/存储的数据位于辅助存储设备上时,将使用这种类型的树,因为它们允许将大量数据存储在节点中。

A B-tree of order m is a multiway search tree in which:

m阶的B树是一个多路搜索树,其中:

The root has at least two subtrees unless it is the only node in the tree. Each nonroot and each nonleaf node have at most m nonempty children and at least m/2 nonempty children. The number of keys in each nonroot and each nonleaf node is one less than the number of its nonempty children. All leaves are on the same level.

除非它是树中唯一的节点,否则根至少有两个子树。每个非根节点和每个非叶节点最多有m个非空的子节点和至少m / 2个非空节点的子节点。每个非根节点和每个非叶节点中的键数比其非空子节点数少一个。所有叶子都处于同一水平。

#1