A database is provided in which an index for the database is provided as a hierarchical structure of nodes that are navigated during a search until a conclusion set is reached. The structure is organized such that key information relating to a node is inferred from the position of the node in the structure. The index is queried using a search criterion having at least one key, each key including at least one key symbol, in order to locate data matching the search criterion. The index is a hierarchical structure of nodes that is navigated during a search until a conclusion set satisfying the search criterion is reached, and the index is searched by comparing, at each node, a decision group within the search key with a decision value associated with the node. The structure is organized such that the key symbols are not stored at a node in the structure, and each node has less than three exit paths therefrom.