B-trees were introduced by Bayer and McCreight. They are a special m-ary balanced tree used in databases because their structure allows records to be inserted, deleted, and retrieved with guaranteed worst-case performance. An n-node B-tree has height O(lg n), where lg is the logarithm to base 2. The Apple® Macintosh® (Apple, Inc., Cupertino, CA) HFS filing system uses B-trees to store disk directories. A B-tree satisfies the following properties: 1. The root is either a tree leaf or has at least two children. 2. Each node (except the root and tree leaves) has between ⌈m/2⌉ and m children, where ⌈x⌉ is the ceiling function. 3. Each path from the root to a tree leaf has the same length.

red-black tree | tree