The data in the database is stored in a data structure that resembles a tree.

A tree data structure consists of nodes. Each node in the tree, except for a special node called the root, has one parent node and one or more child nodes. The root node has no parent. A node that has no child node is called a leaf; a non-leaf node is called an internal node. The level of a node is defined as one more than the level of its parent, with the level of the root node being zero.

C/SIDE Data Structure

The data structure used in the C/SIDE database is called a B+ tree. This means that the tree structure is balanced and that the data (records) are stored only in the leaf nodes, not in the internal nodes. A balanced tree has the advantage that it always contains the minimum number of levels necessary to contain the nodes, so all search paths will be the shortest possible. A B+ tree structure is an efficient data structure that enables fast searches to be performed.


For this example, the tree structure in your database contains a branch with customers A, B, and C, with two free database blocks available.

Assume that you need to modify customer A and C. When you update the records, the DBMS makes a copy of the original. The copies will use two free database blocks. You will then modify the copies, and a new internal node is created.

If an error occurs during the transaction, or the user decides to abort the changes, the database blocks occupied by the copied branch will be freed and be available for new database updates.

If the transaction is committed, this new internal node will replace the old node, and the database blocks used by the old versions of customer A and C will now be available as free database blocks that can be used by database updates.

The database contains a number of historical versions. Gradually, as the free area in the database is consumed by succeeding historical versions, new versions begin to replace the oldest versions.

Slow operations may have performance issues in this environment. Suppose Application X is reading data from the latest version, while generating a very time-consuming report. In the meantime, Application Y begins performing write transactions which consist of order entries.

Newer versions of the database are created as the order entries are added to the database. The maximum number of historical versions in your database depends upon the space in the database that currently is not used by the newest version, that is:

  • The maximum defined size of the database.

  • The amount of space currently used to hold the newest version.

  • Space available for historical versions.

At some point, the data version accessed by X becomes the oldest complete data version. But Y needs a database block from this version to complete its modifications.

This conflict is solved by the DBMS by giving priority to the write transaction and ejecting application X. The following run-time error message is sent to X on the next read operation, "Data version is no longer valid". The process is forced to restart with the newest version. As long as Y continues and the space in the database available for historical versions remains the same, X will most likely not be able to generate the report. To solve this problem, you could expand the size of the database.

See Also