From 4875a3dd9b183dcd2256e2abfc4ccf7484c233b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B6rg=20Frings-F=C3=BCrst?= Date: Wed, 7 Dec 2022 13:17:14 +0100 Subject: New upstream version 4.0.2 --- docs/html/xbc7.htm | 153 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100755 docs/html/xbc7.htm (limited to 'docs/html/xbc7.htm') diff --git a/docs/html/xbc7.htm b/docs/html/xbc7.htm new file mode 100755 index 0000000..20a60de --- /dev/null +++ b/docs/html/xbc7.htm @@ -0,0 +1,153 @@ + + +Xbase DBMS Chapter 7 + +

NDX Indices

+

Chapter Updated 11/27/22

+ +The objective of this chapter is to provide information regarding the +basic concepts of how .NDX 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 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 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. +

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

    + +

    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 Xbase 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 Xbase DBMS manipulates and +navigates index files, the following discussion may be helpfull.

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


    + + -- cgit v1.2.3