System and methodology for providing compact B-Tree

In a database system, said database system storing a plurality of data records, an improved method for creating a path-compressed binary trie index of such records, the method comprising:

• adding key values from at least some of the data records to at least one index page;
• for each index page, determining a path-compressed binary trie of key values in said index page, said path compressed binary trie including leaf nodes and non-leaf nodes;
• traversing said path-compressed binary trie and creating a path-compressed binary trie index by performing the substeps of:
• for each non-leaf node of said path-compressed binary trie, storing in a first array a bit offset and information about size of at least one subtree of said each non-leaf node, said bit offset indicating a particular bit value of the given key value to be examined at the non-leaf node during traversal of the index;
• and
• for each leaf node of said path-compressed binary trie, storing in a second array a pointer to a key value.