ug_ch14.htm

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

<p align="center"><font size="2"><img alt=
"dbstar_14-6.gif - 1968 Bytes" border="0" height="63" src=
"dbstar_14-6.gif" width="378"></font></p>
<p align="center"><b>Fig. 14-6. Member Pointer</b></p>
<p>Figure 14-7 shows the logical structure of a set instance
containing three members.</p>
<p align="center"><img alt="dbstar_14-7.gif - 2203 Bytes" border=
"0" height="184" src="dbstar_14-7.gif" width="351"></p>
<p align="center"><b>Fig. 14-7. Three Member Set Instance</b></p>
<p>Since the members of a particular set can be of different record
types, the member record occurrences may reside in different files.
Figure 14-8 shows a possible physical arrangement of the same set
instance. This example shows that the owner record and first member
record are on the same file. They may or may not be the same record
types. The second and third member records are in a different file
and therefore must be different record types.</p>
<p align="center"><b><img alt="dbstar_14-8.gif - 4393 Bytes"
border="0" height="221" src="dbstar_14-8.gif" width="502"></b></p>
<p align="center">Fig. 14-8. Physical Structure of Set Instance</p>
<h4><a name="DataRecord" id="DataRecord"></a>14.2.2.3 Data Record
Organization</h4>
<p><font size="2">When a record is written to a database slot, it
contains much more than just the field values. Table 14-4 shows the
structure of a record.</font></p>
<p align="center"><b>Table 14-4. Record Contents</b></p>
<table cellspacing="0" border="0" cellpadding="7" width="542">
<tr>
<td width="10%" valign="top">
<p><b><font size="2">Offset</font></b></p>
</td>
<td width="11%" valign="top">
<p><b><font size="2">Length</font></b></p>
</td>
<td width="79%" valign="top">
<p><b><font size="2">Contents</font></b></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">0</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">2</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">Record type (index into record table)</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">2</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">Database address of this record</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">6</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">Creation timestamp (if timestamped)</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">10</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">Last update timestamp (if timestamped)</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">(table)</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">One-byte set of optional key flags for every
eight optional keys declared in record</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">(table)</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">12- or 16-byte sets of set pointers</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">(table)</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">12-byte sets of member pointers</font></p>
</td>
</tr>
<tr>
<td width="10%" valign="top">
<p><font size="2">(table)</font></p>
</td>
<td width="11%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="79%" valign="top">
<p><font size="2">Field values</font></p>
</td>
</tr>
</table>
<p align="center"><font size="2"><img alt=
"dbstar_14-9.gif - 5376 Bytes" border="0" height="356" src=
"dbstar_14-9.gif" width="349"></font></p>
<p align="center"><b>Fig. 14-9. Physical Record
Organization</b></p>
<p>In Table 14-4, some offsets are defined as table values. These
are offsets that vary according to the record type. The first six
bytes are fixed, always containing the delete flag, record lock
bit, record type, and database address. These are altered when
records are deleted (see section 14.2.2, "Data File
Organization").</p>
<p>The two highest-order bits in the record id are used for other
purposes. The remaining 14 bits contain the actual record id. The
highest order bit is turned on when the record is deleted because
the whole word is complemented (see the next section). The next
highest bit is turned on when a record lock is applied.</p>
<p>The record id is a number that is used as an index into the
record table, which is detailed in section 14.3, "Database
Dictionary Table Structure."</p>
<p>The database address field contains the physical address of the
record. This is used for consistency checking. If the record is
deleted, this field will contain the slot number of the next record
in the delete chain.</p>
<p>A timestamped record will contain a four-byte creation timestamp
and a four-byte last update timestamp. If a record is not
timestamped, this extra space is not allocated.</p>
<p>If a set is not timestamped, the set pointers will be 12 bytes
long. If it is timestamped, they will be 16 bytes long.</p>
<p>One byte of optional key stored bit flags is allocated for every
eight optional keys declared in the record type. If no optional
keys are declared, no space is allocated.</p>
<p>All portions of a record except the first six bytes are optional
(a record is not required to have any data fields).</p>
<h4><a name="DeleteChain" id="DeleteChain"></a>14.2.2.4 Delete
Chain</h4>
<p><font size="2">When a record is deleted, <b><i>db.*</i></b>
complements the record id (the first two bytes), and places the
slot at the beginning of a linked list called the delete chain. A
complemented value will always be negative and have a one in the
highest order bit, which is used to detect that the record has been
deleted.</font></p>
<p>A pointer to the head of the delete chain is in the header of
each data file (the first four bytes of page zero). Each slot in
the list contains, in the third through sixth bytes, the slot
number of the next slot in the list. The last slot contains a null
slot number (0).</p>
<p>Figure 14-10 shows the logical structure of a delete chain
containing three deleted record slots.</p>
<p align="center"><b><img alt="dbstar_14-10.gif - 1481 Bytes"
border="0" height="120" src="dbstar_14-10.gif" width="319"></b></p>
<p align="center">Fig. 14-10. Example Data File Delete Chain</p>
<p>The physical locations of the slots in the delete chain are not
ordered by their position in the chain. The order of deletion
determines their physical order. You could think of the delete
chain as an abstract stack object or a last-in-first-out list.
During record creation, record slots are consumed from the delete
chain before new slots are allocated. The records are removed from
the head of the chain. The <b>DCHAINUSE</b> runtime option will
enable and disable use of deleted record slots during record
creation (see "Option Settings" in section 5.2.4).</p>
<h3><a name="KeyFile" id="KeyFile"></a>14.2.3 Key File
Organization</h3>
<p><font size="2">In a key file, the first two entries in page zero
contain page numbers. As discussed below, a B-tree allocates or
discards full pages at a time, so the delete chain header points to
a page, and the next pointer contains the page number of the next
page to be allocated from the end of the key file.</font></p>
<h4><a name="Node" id="Node"></a>14.2.3.1 Node Structure</h4>
<p><font size="2">A node, as used here, is a term that is
synonymous with a page of a <b><i>db.*</i></b> key file. The term
is descriptive of its usage in a tree structure composed of
nodes.</font></p>
<p>As in all <b><i>db.*</i></b> pages, a node starts with a
four-byte integer that stores the time of last update. Following
that is a two-byte integer containing the number of currently used
slots in the node. The remainder of a node consists of a sorted
array of fixed-length key slots, followed by a single node pointer
referred to as the orphan pointer.</p>
<p>The orphan pointer is the number of the node containing keys
greater than the highest key in this node. The maximum number of
key slots that may be in one node is determined by the slot size
and node (page) size.</p>
<p>Table 14-5 shows the general layout of one node in a B-tree.</p>
<p align="center"><b>Table 14-5. Key File Node Structure</b></p>
<table cellspacing="0" border="0" cellpadding="7" width="542">
<tr>
<td width="20%" valign="top">
<p><b><font size="2">Offset</font></b></p>
</td>
<td width="20%" valign="top">
<p><b><font size="2">Length</font></b></p>
</td>
<td width="60%" valign="top">
<p><b><font size="2">Contents</font></b></p>
</td>
</tr>
<tr>
<td width="20%" valign="top">
<p><font size="2">0</font></p>
</td>
<td width="20%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="60%" valign="top">
<p><font size="2">Time of last update</font></p>
</td>
</tr>
<tr>
<td width="20%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="20%" valign="top">
<p><font size="2">2</font></p>
</td>
<td width="60%" valign="top">
<p><font size="2">Number of used slots in node</font></p>
</td>
</tr>
<tr>
<td width="20%" valign="top">
<p><font size="2">6</font></p>
</td>
<td width="20%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="60%" valign="top">
<p><font size="2">Slot space</font></p>
</td>
</tr>
<tr>
<td width="20%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="20%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="60%" valign="top">
<p><font size="2">Orphan pointer</font></p>
</td>
</tr>
</table>
<p align="center"><b><font size="2"><img alt=
"dbstar_14-11.gif - 2773 Bytes" border="0" height="191" src=
"dbstar_14-11.gif" width="348"></font></b></p>
<p align="center">Fig. 14-11. B-Tree Node</p>
<h4><a name="KeySlot" id="KeySlot"></a>14.2.3.2 Key Slot
Structure</h4>
<p><font size="2">Besides the key value itself, used slots contain
additional control information used in the maintenance of the
B-tree, as shown in Table 14-6.</font></p>
<p align="center"><b>Table 14-6. Key Slot Structure</b></p>
<table cellspacing="0" border="0" cellpadding="7" width="542">
<tr>
<td width="18%" valign="top">
<p><b><font size="2">Offset</font></b></p>
</td>
<td width="18%" valign="top">
<p><b><font size="2">Length</font></b></p>
</td>
<td width="64%" valign="top">
<p><b><font size="2">Contents</font></b></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><font size="2">0</font></p>
</td>
<td width="18%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="64%" valign="top">
<p><font size="2">Pointer to child node</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="18%" valign="top">
<p><font size="2">2</font></p>
</td>
<td width="64%" valign="top">
<p><font size="2">Key prefix</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><font size="2">6</font></p>
</td>
<td width="18%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="64%" valign="top">
<p><font size="2">Key contents</font></p>
</td>
</tr>
<tr>
<td width="18%" valign="top">
<p><font size="2">variable</font></p>
</td>
<td width="18%" valign="top">
<p><font size="2">4</font></p>
</td>
<td width="64%" valign="top">
<p><font size="2">Database address of source record</font></p>
</td>
</tr>
</table>
<p align="center"><font size="2"><img alt=
"dbstar_14-12.gif - 2280 Bytes" border="0" height="70" src=
"dbstar_14-12.gif" width="402"></font></p>
<p align="center"><b>Fig. 14-12. Key Slot</b></p>
<p>The child pointer is a node number of a node whose key values
are less than the key stored in this slot. If there is no child
node, this field contains a null node pointer (<b>-1L</b>). A node
that has no child nodes is called a leaf node.</p>
<p>The prefix field is an integer value that is assigned by
<b>ddlp</b>, and is unique for each key type. It is used in sorting
the keys so that different key types will be kept completely
distinct when stored in the same key file.</p>
<p>The key contents are a copy of the fields from the data record.
If the key is a struct or compound key, full copies of all
subfields are stored here in the order in which they occur in the
key definition.</p>
<p>The last field in a key slot is the database address of the
key's associated data record. The field values stored in the key
should always match the field values stored in this data record.
This can be confirmed by using <b>dbcheck</b>.</p>
<h4><a name="BTree" id="BTree"></a>14.2.3.3 B-Tree
Organization</h4>
<p><font size="2">As stated above, the used key slots in a node are
sorted. Also, if a child pointer in a key slot is not null, the
node pointed to by the child pointer contains another set of sorted
keys, all of which precede the key value in the slot.</font></p>
<p>A B-tree starts with a root node. The root node is the entry
point into a B-tree and is always page one in a key file. Figure
14-13 shows a B-tree containing 11 nodes, with the root node at the
upper right.</p>
<p align="center"><b><img alt="dbstar_14-13.gif - 7327 Bytes"
border="0" height="278" src="dbstar_14-13.gif" width="434"></b></p>
<p align="center">Fig. 14-13. Example B-Tree</p>
<p>Note that the used slots field, shown at the top of the node,
identifies the number of keys in the node, even though there may be
room for many more keys in the node.</p>
<p>Note also that there is one more child pointer in a node then
there are keys. This last child pointer is called an orphan pointer
and points to a node containing keys that succeed the key value in
the last filled key slot in this node. It is called an orphan
because it has no key value associated with it.</p>
<p>The maximum number of key slots that may be filled in a node is
computed as:</p>
<div style="margin-left: 4em">
<p><i>maximum slots = (page size - 10) / slot size</i></p>
</div>
<p>where 10 is the sum of the node header, containing the update