Xbase DBMS Chapter 7

NTX Indices

Chapter Updated 2/12/99

The objective of this chapter is to provide information regarding the basic concepts of how .NTX index files work in the Xbase environment.

The information in this chapter has been gathered by searching the internet and by examining the structure of known good NTX indexes.

NTX Index File Characteristics

NTX indices maintain keys in ascending sort order only.
NTX indices support unique or non unique keys.

Unique keys must be unique. The database update routines will fail if an attempt to add a non-unique key is performed.

Non-unique 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.
NTX indexes are automatically updated by the Xbase library after the indices are opened.
Character keys are left justified and padded on the right with spaces.
Numeric keys are stored as eight byte double values.

The numeric key processing logic performs floating point numeric calculations on eight byte double values. This logic may be compute intensive and slow on older machines, especially the older intel processors without a math coprocessor chip.

NTX File Internals

NTX files are comprised of two or more 1024 byte blocks or nodes of information. There are three types of nodes: Head Nodes, Interior Nodes and Leaf Nodes.

The Head Node is the first node in the file starting at position zero (0) and contains information about the NTX file. There is only one Head Node in each index and it always starts at the beginning of the file.

NTX Header Node
Type	Size	Field Name	Description
xbShort	2	Signature Byte	The Clipper signature byte. 0x003h indicates Clipper 87. 0x006h indicates Clipper 5.x
xbShort	2	Indexing Version Number	Documented as the "Compiler Version" but I have observed an increasing number. Incremented whenever the index is changed.
xbLong	4	First Node Offset	The offset to the first node.
xbLong	4	First Unused Page Offset	The offset to the first unused node.
xbShort	2	Key Size + 8	The Key Size plus 8 bytes.
xbShort	2	Key Size	The size (length) of the key.
xbShort	2	Number of Decimals	Number of decimal places in key.
xbShort	2	Max Items Per Node	The maximum number of key per node.
xbShort	2	1/2 The Max Items Per Node	Half the maximum number of key per node. Important in a B-tree system, as this is the minimum number of keys that must be on a page.
char	256	KeyExpression	Key expression string
char	1	Unique	Unique indicator 00 - Not Unique - XB_NON_UNIQUE 01 - Unique - XB_UNIQUE
char	745	Unused	Unused
	1024		Total bytes in node

The following structure is used by the Xbase NTX routines: struct NtxHeadNode { /* ntx header on disk */ xbUShort Signature; /* Clipper 5.x or Clipper 87 */ xbUShort Version; /* Compiler Version */ /* Also turns out to be */ /* a last modified counter */ xbULong StartNode; /* Offset in file for first node */ xbULong UnusedOffset; /* First free node offset */ xbUShort KeySize; /* Size of items (KeyLen + 8) */ xbUShort KeyLen; /* Size of the Key */ xbUShort DecimalCount; /* Number of decimal positions */ xbUShort KeysPerNode; /* Max number of keys per node */ xbUShort HalfKeysPerNode; /* Min number of keys per node */ char KeyExpression[256]; /* Null terminated key expression */ unsigned Unique; /* Unique Flag */ char NotUsed[745]; };

Interior and Leaf Nodes

NTX files use a B-tree system to store keys. A B-tree is a balanced, on disk tree who's design minimizes disk access. Interior Nodes and Leaf Nodes share the same structure in an NTX file. The difference is that interior nodes point to other nodes. Leaf nodes point to nothing. Keys in both interior nodes and leaf nodes point to records in a DBF file. 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.

Leaf nodes have 0 in the LeftNodeNo field.

NTX Interior Node and Leaf Node Structure
Type	Size	Field Name	Description
xbShort	2	NoOfKeysThisNode	The number of key values in this node. (N)
Array of xbUShort	2	offsets[]	Array of HeadNode.KeysPerNode +1 unsigned longs. These values are the offsets (in bytes) of each key in this node, from the beginning of the node.
char	variable	KeyRecs	A repeating structure of pointers and keys. See the next table for the KeyRec structure.

One primary difference between NDX files and NTX files is that NTX files uses an array of offsets on all interior and leaf nodes. Each offset is the byte count from the beginning of the node where each KeyRec will be found. The order of the array of offsets determines the order of keys on a given node. When keys are added or deleted, thus changing the order of the keys on a node, only the order of the offset array is changed. All other key data is not moved. This results in slightly better index performance.

KeyRec Structure
Type	Size	Field Name	Description
xbLong	4	LeftNodeNo	The node number (offset from beginning of file) of the lower node for this key. 0 in Leaf Nodes.
xbLong	4	DbfRecNo	The DBF record number for this key. 0 in Interior Nodes.
char	KeyLen	KeyValue	The key value.

For those interested in knowing how the Xbase DBMS manipulates and navigates index files, the following discussion may be helpfull.

Xbase DBMS navigates through NTX 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. It continues down the tree, adding the nodes to the in-memory node chain until it reaches the correct 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.

Author: Bob Cotton - bob@synxis.com

NTX Indices

NTX Index File Characteristics

NTX File Internals

NTX Header Node

Interior and Leaf Nodes

NTX Interior Node and Leaf Node Structure

KeyRec Structure