XStorage Database Structure

The XStorage database stores data items in chains (rather than individually) so that related items stay together.  This could be considered as an analog for tables inside relationship database.

Simple database operations, such as adding new items or replacing and deleting old items, do not require B+ trees. These come into play when you want to sort data items or search the database for a given item.

A B+ tree is a data structure that is used to implement a very efficient method for sorting large amounts of data; B+ trees enable a correspondingly efficient searching algorithm. You can think of a B+ tree as providing an index to a database, which is why B+ trees are sometimes referred to as indices.

In XStorage, a B+ tree resides in an external database. Each entry in a B+ tree consists of a pair of values: a key string and an associated database reference number. The XDocument API may then be used to insert this key and the database reference number corresponding to this record into a B+ tree.

B+ trees are also balanced; this means that the search paths to each key in the leaves of the tree have the same depth. Because of this feature, a search for a given key among more than a million keys can be guaranteed, even in the worst case, to require accessing the disk only a few times-depending on how many keys are stored at each node.