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 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

TypeSizeField NameDescription
xbShort2Signature ByteThe Clipper signature byte. 0x003h indicates Clipper 87. 0x006h indicates Clipper 5.x
xbShort2Indexing Version NumberDocumented as the "Compiler Version" but I have observed an increasing number. Incremented whenever the index is changed.
xbLong4First Node OffsetThe offset to the first node.
xbLong4First Unused Page OffsetThe offset to the first unused node.
xbShort2Key Size + 8The Key Size plus 8 bytes.
xbShort2Key SizeThe size (length) of the key.
xbShort2Number of DecimalsNumber of decimal places in key.
xbShort2Max Items Per NodeThe maximum number of key per node.
xbShort21/2 The Max Items Per NodeHalf 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.
char256KeyExpressionKey expression string
char1UniqueUnique indicator
00 - Not Unique - XB_NON_UNIQUE
01 - Unique - XB_UNIQUE
1024Total 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

TypeSizeField NameDescription
xbShort2NoOfKeysThisNodeThe number of key values in this node. (N)
Array of xbUShort2offsets[]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.
charvariableKeyRecsA 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

TypeSizeField NameDescription
xbLong4LeftNodeNoThe node number (offset from beginning of file) of the lower node for this key. 0 in Leaf Nodes.
xbLong4DbfRecNoThe DBF record number for this key. 0 in Interior Nodes.
charKeyLenKeyValueThe 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

(c) 1997 StarTech and (c)1999 SynXis Corp.