The index of a DP4 database is organised as a dynamic B-Tree structure. A B-Tree is a balanced multiway tree, in which the parent nodes contain several records and pointers to the child nodes below.
To locate a key, the database manager starts with the root node and compares the key it is searching for with the keys in the nodes following the pointers down through the tree until the correct node is found. A new key is inserted into the tree by moving to the correct point in the tree, moving the existing nodes to the right and putting in the new key and pointer.
A B-Tree provides one of the most efficient ways of organising an index.