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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
|
<!DOCTYPE HTML PUBLIC>
<html>
<title>Xbase DBMS Chapter 5</title>
<body BGCOLOR=#FFFFFF>
<H1><p align="center">Index Overview</p></H1>
<p align="center">Chapter Updated 04/29/23</p><hr>
The objective of this chapter is to provide information regarding
the basic concepts of index processing for the Xbase library.<br><br>
<h3>Overview</h3>
The Xbase64 library is designed to support multiple index types simultaneously.
Dbase, Clipper and Foxbase each had their own index formats and ultimately the
goal is to provide support for all the legacy index file formats.
<br><br>
The 4.0.x rewrite includes the NDX and MDX formats. Earlier versions of the
library included an NTX format which will be brought forward into the
library rewrite at some point in the future.
<h3>Tags</h3>
Each index file contains one or more tags depending on the file type. Each tag is a sort order
and has characteristics: Sort order (ASC or DESC), unique or not unique and some formats support filtering.
Each open table (dbf file) has an "active tag" for database operations.
<h3>Index processing design</h3>
The library is construcuted to handle index files with multiple tags per file. Single tag files like the NDX indices
are treated as a multi tag file, but there is only one tag. This allows for maximum flexibility for future
additional index types.
<h3>Index updates</h3>
The library automatically updates all tags in all open index files.
<br><br>
<h3>Index File Types</h3>
<table border=1>
<tr><th>File<br>Type</th><th>Source</th><th>Max Tags<br>Per File</th><th>Auto Opened</th><th>Sort Order</th><th>Unique Keys</th>
<th>Reclaimed Nodes</th><th>Filter Support</th><th>Status</th></tr>
<tr>
<td>NDX</td><td>dBase</td>
<td><center>1</center></td>
<td><center>Optional</center></td>
<td>ASC only</td>
<td><center>Y</center></td>
<td><center>N</center></td>
<td><center>N</center></td>
<td><center>Available in 4.0.1</center></td>
</tr>
<tr>
<td>MDX</td><td>dBase</td>
<td><center>47</center></td>
<td><center>Yes</center></td>
<td><center>ASC or DESC</center></td>
<td><center>Y</center></td>
<td><center>Y</center></td>
<td><center>Y</center></td>
<td><center>Available in 4.0.1</center></td>
</tr>
<tr>
<td>NTX</td>
<td>Clipper</td>
<td><center>1</center></td>
<td><center>Optional</center></td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center>Pending retrofit</center></td>
</tr>
<tr>
<td>CDX</td>
<td>Fox Pro</td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center></center></td>
<td><center>Pending development</center></td>
<tr>
<tr>
<td>IDX</td><td>Fox Pro</td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td>Pending development</td>
<tr>
</table>
<br><br>
<h3>Index/Tag Methods</h3>
<table border=1>
<tr><th width=45%>Method</th><th>Description</th></tr>
<tr>
<td>xbInt16 xbDbf::CheckTagIntegrity( xbInt16 iTagOpt, xbInt16 iOutputOpt )
</td><td>Checks a tag for missing or duplicate entries. Available if XB_DEBUG_SUPPORT is on.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::CloseIndexFile( xbIx *pIx )
</td><td>Close an index file. Indices are automatically closed when the table is closed.
<br>Not typically called in an application program.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::CreateTag( const xbString &sIxType, const xbString &sName, const xbString &sKey, const xbString &sFilter,
xbInt16 iDescending, xbInt16 iUnique, xbInt16 iOverLay, xbIx **xbIxOut, void **vpTagOut );
</td><td>Create a new tag.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::DeleteTag( const xbString &sIxType, const xbString &sName )
</td><td>Delete existing tag.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::Find( xbString &sKey )<br>xbInt16 xbDbf::Find( xbDate &dtKey )<br>xbInt16 xbDbf::Find( xbDouble &dKey )
</td><td>Find key value for the active tag.</td>
</tr>
<tr>
<td>xbIx * xbDbf::GetCurIx() const
</td><td>Returns a pointer to the current index object.</td>
</tr>
<td>xbString & xbDbf::GetCurIxType() const
</td><td>Returns the current index type.</td>
</tr>
</tr>
<td>void * xbDbf::GetCurTag() const
</td><td>Retrieve pointer to the current active tag.</td>
</tr>
<tr>
<td>const xbString & xbDbf::GetCurTagName() const
</td><td>Returns the current tag name.</td>
</tr>
<td>xbInt16 xbDbf::GetFirstKey()
</td><td>Retrieve the first key for the active tag.</td>
</tr>
<tr>
<td>xbIxList * xbDbf::GetIxList() const
</td><td>Returns a pointer to the list of active indices.
</tr>
<tr>
<td>xbInt16 xbDbf::GetLastKey()
</td><td>Retrieve the last key for the active tag.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::GetNextKey()
</td><td>Retrieve the next key for the active tag.</td>
</tr>
<tr>
<td>xbInt32 xbDbf::GetPhysicalIxCnt() const
</td><td>Returns count of number of physical files opened for DBF table.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::GetPrevKey()
</td><td>Retrieve the previous key for the active tag.</td>
<tr>
<td>xbLinkListNode<xbTag *> * xbDbf::GetTagList() const
</td><td>Returns pointer to linked list of open tags for the DBF file/table.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::OpenIndex( const xbString &sIxType, const xbString &sIndexName )
</td><td>Open an index file. Only used for index files that aren't automatically opened.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::Reindex( xbInt16 iTagOpt )
</td><td>Rebuild a tag. Available if XB_DEBUG_SUPPORT is on.</td>
</tr>
<tr>
<td>xbInt16 xbDbf::SetCurTag( const xbString &sTagName )<br>
void xbDbf::SetCurTag( const xbString &sIxType, xbIx *pIx, void *vpTag )
</td><td>Set current tag.</td>
</tr>
</table>
<br><br>
<h3>Internal Data Storage</h3>
<table border=1>
<tr><th>Type<th>Stored in DBF as</th><th>Stored in NDX as</th><th>Stored in MDX as</th></tr>
<tr><td>C</td><td>Character data</td><td>Character data</td><td>Character data</td></tr>
<tr><td>F</td><td>Text numbers</td><td>xbDouble</td><td>xbBcd</td></tr>
<tr><td>N</td><td>Text numbers</td><td>xbDouble</td><td>xbBcd</td></tr>
<tr><td>D</td><td>Text YYYYMMDD</td><td>xbDouble Julian</td><td>xbDouble Julian</td></tr>
</table>
<br><br>
<hr>
<h2>NDX Indices</h2>
The objective of this section is to provide information regarding the
basic concepts of how .NDX index files work in the Xbase64 library.
Information in this section has been acquired 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>
<li>Character keys are left justified and padded on the right with spaces.<br>
<li>Numeric keys are stored as eight byte double values.<br>
<li>Date kets are stored as julian eigth byte double values.<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 Xbase64 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 Xbase64 DBMS manipulates and
navigates index files, the following discussion may be helpfull.<br><br>
Xbase64 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.
<br><br>
<hr>
<h2>MDX Indices</h2>
The objective of this section is to provide information regarding the
basic concepts of how .MDX index files work in the Xbase64 library.<br>
Information for MDX files has been gathered by searching the internet
and by examining the structure of known good MDX index files.<br><br>
<h4>MDX Index File Characteristics</h4>
<li>MDX files are the same name as the corresponding DBF file with an MDX extension.
<li>MDX files are automatically opened by the library when the DBF file is opened.
<li>MDX index files (aka prod indices) contain from one to 47 tags, where each tag has it's own key characteristics.
<li>MDX indices maintain keys in either ascending or descending sort order.
<li>MDX indices support filtered keys. For example, a filter of <b>.NOT. DELETED()</b> will keep deleted records out
of the index tag.
<li>MDX indices are automatically updated by the Xbase library after the
indices are opened.
<li>MDX 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>Character keys are left justified and padded on the right with spaces.
<li>Numeric keys are stored as twelve byte BCD values.
<li>Date keys are stored as eight byte double julian values.
<h4>MDX File Internals</h4>
The following information is not needed to use the library, it is just included
for general information.<br><br>
MDX files are comprised of 512 pages where multiple pages make a block. The default
setting is 1024 blocks, each block containing two pages.<br><br>
The first four pages contain:
<li>Bytes 0 - 543 contain general file information.
<li>Bytes 544 - 2047 is a 47 item table containing specific tag information.
<br><br>
Pages five and beyound:
<li>Bytes 2048 and beyond contain tag header blocks, interior nodes and leaf nodes.
<br><br>
<h4>Interior and Leaf Nodes</h4>
Interior Nodes and Leaf Nodes share the same structure in an NDX file with
the exception that interior nodes have a non zero number immediately
after the rightmost key on the node.
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 MDX 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 per tag in the file. Leaf nodes
contain DBF record numbers which point to the location of the record
in the DBF file.<br><br>
<hr>
<br><br>
<h2>TDX Indices</h2>
TDX index files are an Xbase64 library specific implementation of indexing which
can be used for creating temporary indices. They can be created as needed and are
automatically deleted when the table/DBF file is closed.<br><br>
TDX files are built on the MDX index logic and supports the following functionality:
<li>Complex Key Expressions
<li>Filters
<li>Unique / Non-unique keys
<li>Ascending / Descending keys
<li>Max of 47 unique temporary index tags
<br><br>
To create a temporary index, set the Type field to "TDX" when using the xbDbf::CreateTag() method.
All other functionality is the same when using temp indices. The only requirement is to set the
type when creating it.<br><br>
Additionally, the create tag only defines the index. If the table is populated with data and
you need the index populated accordingly, use the xbDbf::Reindex() method to bring it up to data after
creating it.
<br><br>
<hr>
<p><img src="xbase.jpg"><br><hr>
</BODY>
</HTML>
|
