Computer Algorithms II Lecture Notes

23 October 2008 • M-way Trees

Outline

• Motivation and definitions.

• 2-3 trees.

  • Binary and red-black trees.

• B-Trees and friends.

Motivation

• Not all hierarchical structures are restricted to two children.

  • Genealogies, organization charts, grammar trees.

• Are binary trees the best structure for 10⁸ nodes?

• Are binary trees the best way to split data between primary and secondary storage?

M-Way Trees

• An M-way tree (a multi-tree, an m-ary tree) is a tree that can have up to M children for a fixed M.

  • M is the tree's (and node's) order, degree or branching factor.

Characteristics

• High-degree trees are less tall than equivalently sized trees of lower degree.

  • 10⁶ ≈ 2²⁰ = 2^2·10 = 4¹⁰.

• Extra children provide slack for shape stability.

  • Shape changes remain local over more operations.

• More information per node.

  • Particularly with B-tree specialization.

M-Way Search Trees

• M-way search trees are defined analogously to binary search trees.

  

• For simplicity, present children appear to the left of absent children.

A Small Trick

• The key sequence k₀, k₁, …, k_i for -1 ≤ i < m is in ascending order.

• It is convenient to assume a key sequence contains the sentinel keys -∞ and +∞

  k_-1 = -∞, k₀, …, k_i, k_{i + 1} = +∞

• For any key value k, -∞ < k < +∞.

• Scanning for i such that k_i ≤ k < k_{i + 1} now has no special cases.

MWST Search

bool search(root, v)

  if root = nil
    return false

  i = scan-keys(v)
  // root.k[i] ≤ v < root.k[i + 1]

  if root.k[i] = v
    return true

  return root.c[i + 1]

MWST Insert

void insert(root, v)

  i = scan-keys(v)  // ki ≤ v < ki+1

  if root.k[i] = v
    return

  if (i = root.k.size() - 1) ∧ (i < m - 2)
     ∧ (root.c[i + 1] = nil)
    root.k[i + 1] = v

  else if root.c[i + 1] = nil
    root.c[i + 1] = new-root(v)

  else
    insert(root.c[i + 1], v)

Comments

• MWST delete is left as an exercise.

• Treating MWST operations analogously to BST operations is not the best way to play it.

  • Details to follow.

2-3 Trees

• A 2-3 tree is a 3-way tree.

  • Two keys and three children.

    

  • Studied by Rudolf Bayer in 1971.

• “2-3” because each non-leaf node in a 2-3 tree always has two or three children.

2-3-Tree Insertion

• Using a quasi-BST insert is not a good idea.

• Consider inserting keys 0, 1, 2, …

  

Which Way Is Up?

• Adding new leaves to a 2-3 tree beneath existing leaves leads to imbalance.

  

• But if you can't grow down, what can you do?

  • The only other direction to grow is up.

• What?

  • Use the key slack!

Full-Node Splitting

• When a node is full, split it and redistribute the keys between the two new nodes.

  

  • Each new node has space for new keys.

  • The median key is inserted into the parent. (Recursion!)

    • The parent may need to be created.

Revised 2-3-Tree Insertion

• Insert the keys 0, 1, 2, …

  

2-3-Tree Deletion

• Deleting from a 2-3 tree is similar to BST deletion.

  • For interior nodes, replace with the min of the max subtree or vice versa.

  • For leaves, just remove keys.

• Eliminating empty nodes while maintaining balance introduces much case analysis.

2-3-Tree Deletion Examples

Binary and 2-3 Trees

• Non-full 2-3 tree nodes waste space.

  • A large tree of them wastes a lot of space.

• Binary tree nodes waste less space, particularly key space.

• Is there any relation between binary and 2-3 tree nodes?

Binary Nodes as 2-3 Nodes

• Leaf nodes are leaf nodes.

  

• Partial interior nodes are full trees.

  

• Full interior nodes are sibling trees.

  

2-3 and Red-Black Trees

• Translate a 2-3 tree into the binary tree T_b.

• The horizontal links in T_b are infrastructure links.

  • They don't point to data, but implement 2-3 nodes.

• Color the horizontal links in T_b red to get the equivalent red-black tree.

Another Small Trick

• An m-way tree node can be implemented with binary tree nodes.

  

Binary and M-way Nodes

• This is the child-sibling representation.

  

• Binary trees can implement unbounded m-way trees with good space efficiency.

  • Although a child-sibling tree is harder to manipulate than is the equivalent n-way tree.

Large Data

• Are binary trees good for holding lots (10⁷ and up) of large (10³ bytes and up) records?

  • So much data that some of it has to be placed in secondary storage.

  • Alternatively: data that must persist between program executions.

Slow Data

• Data moves between primary and secondary storage in moderately-sized (2⁸ to 2¹² bytes) pages.

• Data moves more slowly (at least ×10²) between primary and secondary storage than within the system itself (within primary store).

• Is this the best environment for binary trees?

Big Binary Trees

• Big binary trees have to be segmented into pages when stored externally.

  

• Segmenting binary trees results in poor paging performance and poor cache performance.

Better Tree Segmenting

• Well-behaved tree segments should

  • be dense (requiring few traversals),

  • have related information in the same segment, and

  • have low-traffic links to other segments.

• As m grows, m-way tree nodes become better segments.

B-Trees

• Developed by Rudolf Bayer in 1970.

• A B-tree of order m is a 2m-way search tree with the following properties:

  • Every node (except the root) has at least m keys (leaves sometimes excepted).

  • All leaves have the same depth.

  • Every interior node, including the root, with k keys has k + 1 children.

B-Tree Examples

• Binary-tree nodes are order 1 B-tree nodes.

• Not order-2 B-trees:

  

B-Tree Operations

• The B-tree operations find(), add(), and remove() are essentially those of the 2-3 tree.

• Operations maintain the B-tree property:

  • All leaves at level l.

  • Each node with n ≤ k ≤ 2n keys and k + 1 children.

• Operation variations abound to exploit local properties.

B*-Trees

• The B*-tree is a variation on the B-tree.

• Each node in a B*-tree of order n has at least 2n/3 children.

• There are many games to be played with free space in B-tree nodes and empty B-tree nodes.

Denser Nodes

• Keys are usually smaller (by ×10 at least) than records.

• More keys than records will fit in a node (page) of given size.

• Separate keys from records.

  • Store keys in interior nodes.

  • Store records in leaves.

• Traversal costs drop from O(log_2m n) to O(log_20m n), for example.

Sequential Data Access

• Many applications need efficient sequential access to tree data.

• Tree traversal, even under high branching factors, is not efficient.

  • Between page movement may cause disk I-O.

• All the records are in the leaves and in order.

  • Add secondary links in the leaves for form a linked list.

B⁺-Trees

• A B⁺-tree is a B-tree in which

  • Leaves contain records and interior nodes contain keys.

  • Leaves are linked together in a list.

  

References

• 2-3-4 Trees, Red-Black Trees, B-Trees, and other Trees (Section 15.3) in ADTs, Data Structures, and Problem Solving with C++ second edition by Larry Nyhoff, Prentice Hall, 2005.

• Multi-Way Trees (Section 4.5) in Algorithms + Data Structures = Programs by Nicklaus Wirth, Prentice Hall, 1976.

• The Ubiquitous B-Tree by Douglas Comer in ACM Computing Surveys, June, 1979.