B-Tree Index Methods in a Binary Relational Database
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
This article describes the management of multiple indexes within a single fixed-block-size file, such as may be used in a Binary Relational Database, implemented on a paging system. A binary relational database is characterized by storing large numbers of "triples" of data such as (S,R,T), where S is an entity that is related, by a named relation, R, to the second entity, T. The triples related to a specific entity, say, S, form a tree structure. The branches from each node of the tree are ordered, and are implemented in the form of a keyed index. For example: Each triple, such as (S,R2,T22), has a corresponding triple (T22,R2',S) representing the inverse relation. (Depending the implementation of the Binary Relational Database there may be up to 5 "inverses" representing the 6 possible access paths to a triple.