💾 Archived View for jb55.com › ward.asia.wiki.org › multiway-trees captured on 2021-12-05 at 23:47:19. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

Multiway Trees

Tree structures lend themselves to external searching, if we choose an appropriate representation for grouped nodes. From Knuth volume 3, section 6.2.4.

See test in javascript. page

page

The b-tree, discovered in 1970, makes both search and update guaranteed efficient. A b-tree of order m satisfies these properties.

Every node has at most m children. * Every interior node has at least m/2 children. * The root has at least 2 children, unless it is a leaf. * All leaves appear on the same level, carry no info. * A nonleaf node with k children has k-1 keys.

A node p with j keys will have j+1 pointers.

Search: if p does not contain k, search non-null pi where k is between ki and ki+1.

Insert: if p is full, split and update p's parent. Add a level when root splits.

Delete: left as exercise 6.

The b+-tree varies k with node level, omits records from interior nodes and links each leaf to its successor for sequential access.

The b*-tree delays splits by moving keys to siblings. When sibling fills, we split two nodes into three, each 2/3 full.

Search Index requires log behavior typically provided by b-tree variations so as to not break in large neighborhoods.

Search Index