summaryrefslogtreecommitdiff
path: root/docs/html/xbc7.htm
diff options
context:
space:
mode:
Diffstat (limited to 'docs/html/xbc7.htm')
-rwxr-xr-xdocs/html/xbc7.htm153
1 files changed, 153 insertions, 0 deletions
diff --git a/docs/html/xbc7.htm b/docs/html/xbc7.htm
new file mode 100755
index 0000000..20a60de
--- /dev/null
+++ b/docs/html/xbc7.htm
@@ -0,0 +1,153 @@
+<!DOCTYPE HTML PUBLIC>
+<HTML>
+<TITLE>Xbase DBMS Chapter 7</TITLE>
+<BODY BGCOLOR=#FFFFFF>
+<H2><p align="center">NDX Indices</p></H2>
+<p align="center">Chapter Updated 11/27/22</p><hr>
+
+The objective of this chapter is to provide information regarding the
+basic concepts of how .NDX index files work in the Xbase environment.<br><br>
+
+The information in this chapter has been gathered by searching the internet
+and by examining the structure of known good NDX indexes.<br><br>
+
+<h4>NDX Index File Characteristics</h4>
+
+<li>NDX indices maintain keys in ascending sort order only.<br><br>
+<li>NDX indices support <em>unique</em> or <em>non unique</em> keys.<br><br>
+
+<em>Unique</em> keys must be unique if the UniqueKeyOption is not set to XB_EMULATE_DBASE.
+If the UniqueKeyOption is set to XB_EMULATE_DBASE, then the database update routines will
+add a record to the table, but not add a corresponding duplicate key to the index tag.
+The UniqueKeyOption is off (don't allow duplicates) by default.
+<br><br>
+
+<em>Non-unique</em> Keys are not required to be unique, duplicate
+keys are allowed if the index is created with the XB_NOT_UNIQUE
+setting. Duplicate keys are stored in record number order.<br><br>
+
+<li>NDX indexes are automatically updated by the Xbase library after the
+indices are opened.<br><br>
+
+<li>Character keys are left justified and padded on the right with spaces.<br><br>
+
+<li>Numeric keys are stored as eight byte double values.<br><br>
+
+<h4>NDX File Internals</h4>
+
+NDX files are comprised of two or more 512 byte blocks or nodes of
+information. There are three types of nodes: Head Nodes, Interior
+Nodes and Leaf Nodes.<br><br>
+
+<li>The <em>Head Node</em> is the first node in the file starting at
+position zero (0) and contains information about the NDX file. There
+is only one Head Node in each index and it always starts at the
+beginning of the file.<br><br>
+
+
+<TABLE BORDER>
+<CAPTION ALIGN="TOP"><h3>NDX Header Node</H3></CAPTION>
+<TR VALIGN="BASELINE">
+<TR><TH ALIGN="LEFT">Type<TD>Size<TD>Field Name<TD>Description
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>StartNode<TD>This identifies the root node of
+ the index. The Header node is node 0.
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>Total Nodes<TD>This is the count of the total
+ nodes in the index. The count includes the header node.
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>NoOfKeys<TD>Total number of keys in the index +1
+<TR><TH ALIGN="LEFT">xbUShort<TD>2<TD>KeyLen<TD>The index key length
+<TR><TH ALIGN="LEFT">xbUShort<TD>2<TD>KeysPerNode<TD>The maximum number of keys per node
+<TR><TH ALIGN="LEFT">xbUShort<TD>2<TD>KeyType<TD>Type of key<br>
+00 - Character<br>01 - Numeric
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>Keysize<TD>Key record size + 8
+<TR><TH ALIGN="LEFT">char<TD>1<TD>Unknown<TD>Reserved
+<TR><TH ALIGN="LEFT">char<TD>1<TD>Unique<TD>Unique indicator<br>
+00 - Not Unique - XB_NON_UNIQUE<br>01 - Unique - XB_UNIQUE
+<TR><TH ALIGN="LEFT">char<TD>488<TD>KeyExpression<TD>Key expression string
+<TR><TH ALIGN="LEFT"><TD>512<TD><TD>Total bytes in node
+</TABLE>
+<br><br>
+The following structure is used by the Xbase NDX routines:
+<xmp>
+ struct NdxHeadNode{
+ xbLong StartNode; /* header node is node 0 */
+ xbLong TotalNodes; /* includes header node */
+ xbLong NoOfKeys; /* actual count + 1 */
+ xbUShort KeyLen; /* length of key data */
+ xbUShort KeysPerNode; /* max number of keys per node */
+ xbUShort KeyType; /* 00 = Char, 01 = Numeric */
+ xbLong KeySize; /* KeyLen + 8 */
+ char Reserved1; /* Not sure about this one */
+ char Unique; /* 00 = not unique, 01 = unique*/
+ char KeyExpression[488]; /* key definition */
+ }
+</xmp>
+<br><br>
+
+<h4>Interior and Leaf Nodes</h4>
+
+Interior Nodes and Leaf Nodes share the same structure in an NDX file.
+The difference between the two types is that interior nodes point to
+other interior nodes or leaf nodes and leaf nodes point to records in
+a DBF file. Interior nodes are optional nodes in an NDX file,
+however if there are more than a few keys in the index there will
+certainly be one or more interior nodes in the file. There will
+always be at least one leaf node in the file. Leaf nodes contain DBF
+record numbers which point to the location of the record in the
+DBF file.<br><br>
+
+Interior nodes have field LeftNodeNo valued which points to the node
+which points to the keys which are less than the key value in the KeyVal
+field. There is one more LeftNodeNo value in the node than there are keys.
+The Last LeftNodeNo points to the node which is greater than the highest
+key value in the node. Interior nodes have 0 in the value for the
+DbfRecNo field.<br><br>
+
+Leaf nodes have 0 in the LeftNodeNo field but do have a value in the
+DbfRecNo field which points to a DFB record.<br><br>
+
+
+<TABLE BORDER>
+<CAPTION ALIGN="TOP"><h3>NDX Interior Node and Leaf Node Structure</H3></CAPTION>
+<TR VALIGN="BASELINE">
+<TR><TH ALIGN="LEFT">Type<TD>Size<TD>Field Name<TD>Description
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>NoOfKeysThisNode<TD>The number of key values in this node.
+<TR><TH ALIGN="LEFT">char<TD>508<TD>KeyRec<TD>A repeating structure of
+ pointers and keys. See the next table for the KeyRec structure.
+</TABLE>
+<br><br>
+<TABLE BORDER>
+<CAPTION ALIGN="TOP"><h3>KeyRec Structure</H3></CAPTION>
+<TR VALIGN="BASELINE">
+<TR><TH ALIGN="LEFT">Type<TD>Size<TD>Field Name<TD>Description
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>LeftNodeNo<TD>The node number of the lower node
+ for this key. 0 in Leaf Nodes.
+<TR><TH ALIGN="LEFT">xbLong<TD>4<TD>DbfRecNo<TD>The DBF record number for this key.
+ 0 in Interior Nodes.
+<TR><TH ALIGN="LEFT">char<TD>KeyLen<TD>KeyValue<TD>The key value.
+</TABLE>
+
+<br><br>
+For those interested in knowing how the Xbase DBMS manipulates and
+navigates index files, the following discussion may be helpfull.<br><br>
+
+Xbase DBMS navigates through NDX files by using an in-memory chain
+of nodes of the current location / key in use. It starts by reading the
+Head Node of the index, which points to the first node of the file. The
+first node of the file will be a leaf node if the index is small or will
+be an interior node if the index has more than one leaf node. The first
+interior node is loaded into memory, added to the node chain and points
+to the next node to read. The node is made up of one or more keys. If
+it is a leaf node, the logic looks for a matching key on the node.
+Otherwise, if it is an interior node, the logic looks at the keys until the
+search key is greater than or equal to the key in the node and then
+traverses down the tree to the next node. It continues down the tree,
+adding the nodes to the in-memory node chain until it reaches the correct
+leaf node. If it finds a matching key in the leaf node, it returns a
+XB_FOUND condition. If it doesn't find an exact match in the leaf node, it
+returns a XB_NOT_FOUND condition and stops on the key which is greater than
+the search key given.
+
+<hr>
+<p><img src="xbase.jpg"><br><hr>
+</BODY>
+</HTML>