ug_ch14.htm

db.* (pronounced dee-be star) is an advanced, high performance, small footprint embedded database fo

time (four bytes), used slots count (two bytes), and the orphan
pointer (four bytes).</p>
<p>When the root node in the B-tree is filled to its maximum size,
it will split into three nodes: the original root node, which will
contain only one key, and the two nodes at the next level in the
tree, which will contain the remainder of the keys from the
original root node.</p>
<p>As a B-tree grows, the non-root nodes will also be filled. As
each node fills, it will split into two nodes. Rather than leaving
one key in the node and creating two child nodes (as is done with
the root node), the one remaining (middle) key is inserted into the
node in the next level up in the tree. Hence, the two new nodes
created by splitting one node are at the same level in the tree,
and the tree remains balanced.</p>
<p>If enough nodes at a lower level split, the root node will again
become filled with keys, and need to split. It will split again in
the same way, leaving two nodes just beneath it. This action
increases by one the number of levels in the tree. This is
important because, at most, one database read is required per level
in the B-tree. The more levels in a B-tree, the more input and
output are required in using it. Fewer levels are needed as more
key slots per node are available.</p>
<p>Just as the addition of keys to the B-tree causes additional
nodes to be used, the deletion of keys will eventually cause nodes
to be emptied and discarded. During key deletion, two nodes may
combine into one node. This operation is effectively the inverse of
a node split. The unused node is placed into the key file's delete
chain.</p>
<h4><a name="DeleteChain2" id="DeleteChain2"></a>14.2.3.4 Delete
Chain</h4>
<p><font size="2">When a node is discarded during a key deletion,
it is placed at the head of the delete chain. As new nodes are
required, they are first taken from the delete chain and then, if
the delete chain is empty, assigned from the end of the
file.</font></p>
<p>The delete chain pointer is stored in the first four bytes of
page zero in a key file. If the delete chain header does not
contain a null node pointer (-1L), it contains the node number of
the first node in the chain. Each node in the chain will contain
the node number of the next node in bytes four through seven. The
last node in the chain will contain a null as the pointer to the
next node.</p>
<p>Figure 14-14 shows how a delete chain in a key file may
appear.</p>
<p align="center"><b><img alt="dbstar_14-14.gif - 1957 Bytes"
border="0" height="214" src="dbstar_14-14.gif" width="317"></b></p>
<p align="center">Fig. 14-14. Example Key File Delete Chain</p>
<h2><a name="Dictionary" id="Dictionary"></a>14.3 Database
Dictionary Table Structure</h2>
<p><font size="2">This section describes the structure of the
tables that <b><i>db.*</i></b> uses to access and modify the
contents of the files discussed in the previous section.</font></p>
<p>The source code for the definitions given below is in the
<b><i>db.*</i></b> header file <b>dbtype.h</b>. The table structure
definitions are given using C <b>typedef</b> statements.</p>
<p>A common type definition that is used in the table definitions
is <b>DB_SHORT</b>. This is used instead of the standard <b>int</b>
when a 16-bit integer is required. The type definition of
<b>DB_SHORT</b> will always be set (in <b>db.star.h</b>) to the
native 16-bit type for a machine (normally <b>short</b>).</p>
<h3><a name="Contents" id="Contents"></a>14.3.1 Contents of the
Dictionary File</h3>
<p><font size="2">The dictionary file is created by <b>ddlp</b> and
contains the tables that are created from a DDL file. The name of
the dictionary file is the database name followed by
<b>.dbd</b>.</font></p>
<p>The dictionary file contains the following information in the
order described:</p>
<table cellspacing="0" border="0" cellpadding="7" width="542">
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">version</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">0</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">6</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Version number of <b><i>db.*</i></b></font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">page_size</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">6</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Maximum size of database page</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_ft</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">8</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of file table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_rt</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">10</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of record table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_fd</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">12</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of field table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_st</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">14</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of set table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_mt</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">16</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of member table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_srt</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">18</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">contents</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">Number of sort table entries</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">&nbsp;</td>
<td width="82%" valign="top">&nbsp;</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">name</font></b></p>
</td>
<td width="82%" valign="top">
<p><b><font size="2">size_kt</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">offset</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">20</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><b><font size="2">length</font></b></p>
</td>
<td width="82%" valign="top">
<p><font size="2">2</font></p>
</td>
</tr>
<tr>