这是 2-3 树的确切定义

Question

抱歉，我不会post图片，所以我用键盘打印它们。

                             [6:-]

               [2:4]                        [8:-]      

     [0:1]     [2:3]    [4:5]         [6:7]       [8:9]

这个来自《数据结构与算法》，是2-3树的图，可以看到父节点上的每一个数据都必须在子节点上。

                             [50:90]

      [20:-]                 [70:-]                  [120:150]

[10:-]    [30:40]       [60:-]    [80:-]    [100:110]   [130:140]   [160:-]

而这个是另一本书《data abstraction and problem solving with c++》的，父节点上的数据不在子节点上。

哪一个是正确的？

Answer 1

这些都是 2-3 棵树，因为“2-3”只是指每个节点具有的 children 个数。但是这些树有不同的更具体的名称。

第一个，其中 parents 从 children 复制密钥，称为 "B+ tree"：https://en.wikipedia.org/wiki/B%2B_tree

第二个 parent 键不是副本，称为 "B tree"：https://en.wikipedia.org/wiki/B-tree

请注意，通常有与键关联的值，而在 B+ 树中，内部节点不包含值。

B+ 树在文件系统支持的数据库索引中很流行。因为内部节点不包含值，它们可以有更高的fan-out，降低树的高度并使访问更快。

叶节点通常也不实际存储值——它们存储指向值存储位置的指针，这方便地为 B+ 树的叶节点提供了与内部节点完全相同的结构。

这是 2-3 树的确切定义

which is the exactly definition of 2-3 tree

tree

b-tree

data-structures