Treffer: Bit-Tree: A Data Structure for Fast File Processing.

This article describes a variant of the B-Tree model called Bit-Tree. The authors describe B-Trees in detail. A Bit-Tree is designed to pack more information into leaf nodes. The denser this information can be compacted, the lower the height of the tree with an attendant reduction in the number of input-output operations required to search the tree. As a by-product, less space is required for the tree. This article will restrict attention to the most common file operations get, add, delete and "get equal or greater." A B-Tree consists of a number of nodes. Each node contains a number of pointers separated by keys. Every branch is either a branch or a leaf node. The pointers in a branch node point to other nodes. One node in the tree is the root node. In Bit-Tree leaf nodes, the key information used is the distinction bit between two consecutive keys. Both Bit-Trees and Prefix B-Trees lose information about the keys. Any technique that loses information about the keys cannot assure that the key searched for is in the file.