Efficient use of trie data structure in databases

A method of retrieving data from an electronic database or information retrieval system, comprising the steps of:

• obtaining representations of two or more first-order input tries, wherein the two or more first-order input tries are higher in a sequence than second-order tries and wherein at least all parent nodes in an input trie comprise a bitmap;
• evaluating at least parts of a first-order resulting trie, the first-order resulting trie being a first combination, using a logical operation, of the first-order input tries, the first combination resulting in a first combined bitmap;
• and
• providing as an output a representation of a resulting trie, a set or a subset of keys and/or other data items associated with nodes of the resulting trie, or a set of keys or values derived from keys associated with nodes of the resulting trie;
• wherein a representation of at least one of the first-order input tries is provided as an output of a second-order combination operator performing the steps of:
• obtaining representations of two or more second-order input tries;
• at least partially evaluating a second-order resulting trie, the second-order resulting trie being a second combination, using a second-order logical operation, of the second-order input tries, the second combination resulting in a second combined bitmap;
• and
• providing as an output a representation of the second-order resulting trie;
• wherein at least parts of the second-order resulting trie are evaluated during the step of evaluating at least parts of the first-order resulting trie, wherein at any given moment during evaluation of a trie or parts of a trie, only those parts of a physical data structure of the trie or of the parts of the trie that need to be realized in that moment for traversing the trie or the parts of the trie are realized;
• wherein parts of the first-order resulting trie and parts of the second-order resulting trie are evaluated in an interleaved manner;
• and
• wherein using a logical operation comprises using a bitwise AND Boolean operation, a bitwise OR Boolean operation, a bitwise AND NOT Boolean operation, or a bitwise XOR Boolean operation.