CSC 3102 Chapter : Csc3102BTrees
Document Summary
Supplementary notes: introduction, b-tree properties, b-tree insertion, b-tree deletion, real-world applications. An m-nary tree is a generalization of the binary tree. The m-ary tree is said to be an mth order tree where each node has at most m children. If k m is the number of children for a given node, then that node must have k 1 keys. An m nary search tree is also a generalization of a binary search tree. A b-tree is a special case of an m-nary search tree. An mth order b-tree is a balanced m-nary search tree in which: leaf nodes are at the same level, all internal nodes except the root have at most m nonempty children, and at least (cid:6) m. 2 (cid:7) nonempty children: each internal node has 1 less key than the number of children that it has, and its keys partition the keys in such a way to preserve the search tree property.
