Index Overview

Chapter Updated 2/11/26

The objective of this chapter is to provide information regarding the basic concepts of index processing for the Xbase64 library.

Overview

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 for this library is to provide support for all legacy XBase index file formats.

The 4.0.x rewrite includes the NDX and MDX (Version 2) formats. Beginning with 4.2.4 MDX (Version 3) support is included. Earlier versions (3.x) of the library included an NTX format which will be brought forward into the library rewrite at some point in the future.

Which version should I use? If you are looking for backward compatibility, the existing application will dictate which version to use and the Xbase64 library can determine by using the xbXBase::Open() method. If you are creating something new, use the latest versions - dbf version 7 which will by default use mdx version 3.

Tags

Each index file corresponds to one database .dbf file and contains one or more tags depending on the index file type. Each dbf file can have zero, one or more associateed index files. Each tag is a sort order and has characteristics: Sort order (ASC or DESC), unique or not unique and the MDX format supports filtering. Each open table (dbf file) has an "active tag" for database operations.

Index processing design

The library is constructed 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.

Index updates

The library automatically updates all tags in all open index files.


Supported Index Versions as of 4.2.4

VersiondBASE ReleseSupported
Key Types		Supported
Sort Order		Supported
Formats		Deleted Records
(Standard dBASE processing)
NDXAll dBASE versions Character
Numeric
Date		Ascending only Non Unique
Unique		 Kept in index
MDX
Version 2		dBASE IV and greater Character
Numeric
Date		 Ascending or
Descending		 Non Unique
Unique		 Kept in index unless excluded with filter
.NOT. DELETED()
MDX
Version 3		dBASE 7 and greater Character
Numeric
Date
Long
Double
TimeStamp		 Ascending or
Descending		 Non Unique
Unique
Distinct
Primary Key		 Disinct and Primary tags exclude deleted records.
Non unique and unique include deleted records unless filtered out.



Supported Formats

FormatDescription (Standard dBASE processing)
Non UniqueIndex will support one or more duplicate key values.
UniqueIf the table contains more than one record with the same key value, the table is updated with the record containing the duplicate key but the index (tag) only contains a reference to the first record in the file.
DistinctIntroduced with MDX V3.
Allows only one record in the table per key value.
Excludes deleted records.
Primary KeyIntroduced with MDX V3.
Allows only one record in the table per key value.
Excludes deleted records.
Only one primary key allowed per table.
Index filters not allowed on primary keys.




Special Xbase64 Index Processing


The original dBASE indexing functionality has some behavior patterns that are inconsistent with modern day relational database management systems. Specifically duplicate keys in a unique index were problematic along with deleted records remaining referenced in index files.

Based on the that, along with user requests version 4.1.8 of the library introduced enhanced index processing to support either legacy dBASE compatibility or enhanced logic for deleted records, unique keys and tag page recycling.

Xbase64 supports two modes of index processing. The standard/default mode implements the standard dBASE type processing as outlined above. The enhanced mode operation is described as follows.


Mode Description Deleted Records Index Tags defined as Unique Node Recycling
XB_IX_DBASE_MODE DBase compatibility mode See above for standard deleted records processing. See above for standard unique key proocessing. None
XB_IX_XBASE_MODE Enhanced index processing. NDX and MDX Version 2, deleted records are removed from the index. NDX and MDX Version 2, attempts to add record with a duplicate key generates an error. MDX Version 2 and MDX Version 3, empty pages recycled.


  • XB_IX_DBASE_MODE is the default setting.
  • XB_IX_XBASE_MODE is not compatible with other XBase or dBASE related tools. It is specific to the XBase64 library only.
  • The two modes are not compatible.
  • When switching modes on a preexisting index, you will need to reindex.
  • If switching to XB_IX_XBASE_MODE, you will need to reindex with the Xbase64 library version. If the tag is defined as unique and multiple records with the same key exist, the reindex routine will throw a XB_KEY_NOT_UNIQUE error.
  • If switching to XB_IX_DBASE_MODE, you are not limited to the XBase64 library version for reindexing.
  • The mode setting is not stored in the physical index file. It needs to be handled by your program in some other manner for every use.
  • This is a tag specific setting meaning different tags can be set to operate in different modes.
  • The mode is designed to be set one way or the other for the entire lifespan of the tag. It's not designed to be switched back and forth.
  • None of the standard dBASE index file formats recycle empty nodes. Using XB_IX_XBASE_MODE can be used to recycle and reuse index nodes. Example: A tag might exclude deleted records. If a large number of records are deleted, it might result in tag pages being emptied out. Instead of leaving orphaned node pages in the file, XB_IX_XBASE_MODE will recycle for the MDX file formats.


    Methods for getting/setting the mode

    MethodDescription
    xbCore::GetDefaultIxTagMode()Get the default mode
    xbCore::SetDefaultIxTagMode( XB_IX_DBASE_MODE ||
    XB_IX_XBASE_MODE )    		Set the default mode. Call during program initialization.
    xbIx::GetIxTagMode( void *vpTag )Get the mode for the specified tag
    xbIx::SetIxTagMode( void *vpTag, XB_IX_DBASE_MODE ||
    XB_IX_XBASE_MODE )    		Set the mode for the specified tag



    More on deleted Records

    With the original dBASE software, deleting a record did not actually delete a record from the DBF database file. Instead of physically removing the record from the file, the record is flagged with an "*" in the first byte of the record and the record is available to be "undeleted" at a later point. Additionally, the orginal dBASE Software does not delete the index values from a given tag if the record is flagged for deletion.

    To physically remove records flagged for deletion from the DBF file, execute the xbDbf::Pack() method.

    For the MDX style indices, deleted records can be filtered out by adding a filter of ".NOT. DELETED()" to the key definition.
    For MDX Version 3 indices, distinct and primary indices exclude deleted records.

    For the NDX style indices, filter logic does not exist. One possible way to address deleted records in a given NDX index would be to add the delete flag to the key structure and filter out deleted records using the actual key value. For example, you could have a key expression defined as DELETED()+MYFIELD, or alternatively MYFIELD+DELETED().

    Setting the mode to XB_IX_XBASE_MODE will remove index entries when the corresponding dbf record is deleted for NDX and MDX Version 2 indices.


    Index File Types

    File
    Type    		SourceMax Tags
    Per File    		Auto OpenedSort OrderUnique Keys Distinct KeysPrimary KeyReclaimed NodesFilter SupportStatus
    NDXdBASE
    1
    Optional
    		 ASC only
    Y
    N
    N
    N
    N
    Available in 4.0.1
    MDX V2dBASE
    47
    Yes
    ASC or DESC
    Y
    N
    N
    Y with
    XB_IX_XBASE_MODE enabled
    Y
    Available in 4.0.1
    MDX V3dBASE
    47
    Yes
    ASC or DESC
    Y
    Y
    Y
    Y with
    XB_IX_XBASE_MODE enabled
    Y
    Available in 4.2.4
    NTX Clipper
    1
    Optional
    Pending retrofit
    CDX Fox Pro
    Pending development
    IDXFox Pro
    Pending development


    Index/Tag Methods

    MethodDescription
    xbInt16 xbDbf::CheckTagIntegrity( xbInt16 iTagOpt, xbInt16 iOutputOpt ) Checks a tag for missing or duplicate entries. Available if XB_DEBUG_SUPPORT is on.
    xbInt16 xbDbf::CloseIndexFile( xbIx *pIx ) Close an index file. Indices are automatically closed when the table is closed.
    Not typically called in an application program.
    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 ); Create a new tag.
    xbInt16 xbDbf::DeleteTag( const xbString &sIxType, const xbString &sName ) Delete existing tag.
    xbInt16 xbDbf::Find( xbString &sKey )
    xbInt16 xbDbf::Find( const char *sKey )
    xbInt16 xbDbf::Find( xbDate &dtKey )
    xbInt16 xbDbf::Find( xbDouble &dKey )     		Find key value for the active tag.
    xbIx * xbDbf::GetCurIx() const Returns a pointer to the current index object.
    xbString & xbDbf::GetCurIxType() const Returns the current index type.
    void * xbDbf::GetCurTag() const Retrieve pointer to the current active tag.
    const xbString & xbDbf::GetCurTagName() const Returns the current tag name.
    xbInt16 xbDbf::GetFirstKey() Retrieve the first key for the active tag.
    xbIxList * xbDbf::GetIxList() const Returns a pointer to the list of active indices.
    xbInt16 xbIx::GetIxTagMode( void *vpTag ) Returns one of XB_IX_DBASE_MODE or XB_IX_XBASE_MODE
    xbInt16 xbDbf::GetLastKey() Retrieve the last key for the active tag.
    xbInt16 xbDbf::GetNextKey() Retrieve the next key for the active tag.
    xbInt32 xbDbf::GetPhysicalIxCnt() const Returns count of number of physical files opened for DBF table.
    xbInt16 xbDbf::GetPrevKey() Retrieve the previous key for the active tag.
    xbLinkListNode * xbDbf::GetTagList() const Returns pointer to linked list of open tags for the DBF file/table.
    xbString &xbIx::GetType() const Returns one of NDX, MDX or TDX.
    xbInt16 xbDbf::OpenIndex( const xbString &sIxType, const xbString &sIndexName ) Open an index file. Only used for index files that aren't automatically opened.
    xbInt16 xbDbf::Reindex( xbInt16 iTagOpt ) Rebuild a tag. Available if XB_DEBUG_SUPPORT is on.
    xbInt16 xbDbf::SetCurTag( const xbString &sTagName )
    void xbDbf::SetCurTag( const xbString &sIxType, xbIx *pIx, void *vpTag )     		Set current tag.
    xbIx::SetIxTagMode( void *vpTag, XB_IX_DBASE_MODE ||
    XB_IX_XBASE_MODE )    		 Set the processing mode for the specified tag.


    Internal Data Storage

    TypeStored in DBF asStored in NDX asStored in MDX V2 asStored in MDX V3 as
    CCharacter dataCharacter dataCharacter dataCharacter data
    FText numbersxbDoublexbBcd12 byte xbBcd
    NText numbersxbDoublexbBcd12 byte xbBcd
    DText YYYYMMDDxbDouble JulianxbDouble Julian12 byte double julian
    ILong IntN/AN/A4 Byte Long
    +Auto IncrementN/AN/A4 Byte Long
    ODoubleN/AN/A8 Byte Double
    @Time StampN/AN/A8 Byte Time Stamp


    NDX Indices

    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.

    NDX Index File Characteristics

  • NDX indices maintain keys in ascending sort order only.

  • NDX indices support unique or non unique keys.

    Unique keys must be unique. If the index processing option is to XB_IX_DBASE_MODE, then the database update routines will allow all records to be added to the table but not add a corresponding duplicate key to the index tag. Set the option to XB_IX_XBASE_MODE if you want the library to to not add duplicate records to an NDX file for a given key value. Keep in mind that deleted records are also kept in the NDX index file.

    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.

  • NDX 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.
  • Date keys are stored as julian eight byte double values.

    NDX File Internals

    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.

  • The Head Node 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.

    NDX Header Node
    TypeSizeField NameDescription
    xbLong4StartNodeThis identifies the root node of the index. The Header node is node 0.
    xbLong4Total NodesThis is the count of the total nodes in the index. The count includes the header node.
    xbLong4NoOfKeysTotal number of keys in the index +1
    xbUShort2KeyLenThe index key length
    xbUShort2KeysPerNodeThe maximum number of keys per node
    xbUShort2KeyTypeType of key
    00 - Character
    01 - Numeric
    xbLong4KeysizeKey record size + 8
    char1UnknownReserved
    char1UniqueUnique indicator
    00 - Not Unique - XB_NON_UNIQUE
    01 - Unique - XB_UNIQUE
    char488KeyExpressionKey expression string
    512Total bytes in node


    The following structure is used by the Xbase64 NDX routines: 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 */ }

    Interior and Leaf Nodes

    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.

    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.

    Leaf nodes have 0 in the LeftNodeNo field but do have a value in the DbfRecNo field which points to a DFB record.

    NDX Interior Node and Leaf Node Structure
    TypeSizeField NameDescription
    xbLong4NoOfKeysThisNodeThe number of key values in this node.
    char508KeyRecA repeating structure of pointers and keys. See the next table for the KeyRec structure.


    KeyRec Structure
    TypeSizeField NameDescription
    xbLong4LeftNodeNoThe node number 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 Xbase64 DBMS manipulates and navigates index files, the following discussion may be helpful.

    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.

    MDX Indices

    The objective of this section is to provide information regarding the basic concepts of how .MDX index files work in the Xbase64 library.
    Information for MDX files has been gathered by searching the internet and by examining the structure of known good MDX index files.

    MDX Index File Characteristics

  • MDX files are the same name as the corresponding DBF file with an MDX extension.
  • MDX files are automatically opened by the library when the DBF file is opened.
  • MDX index files (aka prod indices) contain from one to 47 tags, where each tag has it's own key characteristics.
  • MDX indices maintain keys in either ascending or descending sort order.
  • MDX indices support filtered keys. For example, a filter of .NOT. DELETED() will keep deleted records out of the index tag.
  • MDX indices are automatically updated by the Xbase library after the indices are opened.
  • MDX indices support unique or non unique keys.

    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.

  • Character keys are left justified and padded on the right with spaces.
  • Numeric keys are stored as twelve byte BCD values.
  • Date keys are stored as eight byte double julian values.

    MDX Version 3 enhancements


    MDX Version 3 support, introduced in dBASE 7, includes additional support for the following:
  • Distinct keys
  • Primary keys
  • Double value key types
  • Long value key types
  • Time Stamp value key types

    MDX File Internals

    The following information is not needed to use the library, it is just included for general information.

    MDX files are comprised of 512 pages where multiple pages make a block. The default setting is 1024 blocks, each block containing two pages.

    The first four pages contain:
  • Bytes 0 - 543 contain general file information.
  • Bytes 544 - 2047 is a 47 item table containing specific tag information.

    Pages five and beyound:
  • Bytes 2048 and beyond contain tag header blocks, interior nodes and leaf nodes.

    Interior and Leaf Nodes

    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.



    TDX Indices

    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.

    TDX files are built on the MDX index logic and supports the following functionality:
  • Complex Key Expressions
  • Filters
  • Unique / Non-unique keys
  • Ascending / Descending keys
  • Max of 47 unique temporary index tags

    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.

    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.