1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
<!DOCTYPE HTML PUBLIC>
<HTML>
<TITLE>Xbase DBMS Chapter 6</TITLE>
<BODY BGCOLOR=#FFFFFF>
<H2><p align="center">NDX Indices</p></H2>
<p align="center">Chapter Updated 4/12/04</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. The database update routines will
fail if an attempt to add a non-unique key is performed.<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>
|
