The key type is S_KEY. To create a key a S_CreateKey() function should be used. Given an array of bytes and its length it resets the given key to the specified value.

void S_CreateKey(
        S_KEY * pResKey,
        S_STRING sParValue,
        S_WEIGHT iParLength
     );

Note that one can store not only string-valued keys, but keys of an arbitrary structure by providing a conversion of a user defined key to a byte array. E.g. a number can be easily converted to a string using, say, the C run-time library routines itoa(), or ltoa().

A key weight equals the length of the byte array plus a constant given by S_EMPTY_KEY_WEIGHT.

S_COMPLETION_CODE S_CreateTree(
                    S_TREE_HANDLE * phResTree,
                    S_NAME sParFileName,
                    S_LOCALITY iParB = S_B_DEFAULT,
                    S_ORDER iParQ = S_Q_DEFAULT,
                    S_RANK iParP = S_P_DEFAULT,
                    S_WEIGHT iParMuMax = S_MuMax_DEFAULT
                  );

To create a S(b)-tree it is necessary to specify the following parameters.

	FileName where the tree will be stored.
	b is the locality parameter. The better packing you need the greater b should be.
	q is the order of the S(b)-tree. It specifies a minimal number of keys in a node, and is intended to provide high branching of the tree internal nodes.
	p is the tree rank. It is the size of the block for storing the tree nodes, meaning that a node weight cannot exceed p.
	MuMax characterizes the key set K, in the way that all keys in K have length not greater than MuMax.

A node weight is the sum of weights of keys contained in the node plus constant S_EMPTY_NODE_TREE_WEIGHT. In the implementation we need to store some header for each tree node that contains particularly the number of keys in the node, which is necessary for correct reads of the node. Thus, actually the tree rank according to our definitions above is p - S_EMPTY_NODE_TREE_WEIGHT.

The restrictions for the parameters that provide correctness of the algorithms are as follows:

1. b >= 1
2. q >= b; q >= 2
3. p >= 2q MuMax + S_EMPTY_NODE_TREE_WEIGHT

S_CreateTree() creates an empty S(b)-tree with the specified parameters, forms the tree handle (S_TREE_HANDLE) in the output parameter phResTree, and returns the completion code (S_COMPLETION_CODE) of the function. The tree handle can be used then in other tree functions for specifying the tree the function is applied to. The completion code is S_CC_OK if the tree was successfully created. Otherwise one of the error codes is returned. Particularly, if the specified tree parameters do not satisfy the restriction a parameter inconsistency error code will be returned.

S_COMPLETION_CODE S_LoadTree(
                    S_TREE_HANDLE * phResTree,
                    S_NAME sParFileName
                  );

Another way to get access to a S(b)-tree is to load it.

S_LoadTree() loads the tree located at the specified file, forms the tree handle, and returns a completion code.

S_COMPLETION_CODE S_CloseTree(
                    S_TREE_HANDLE * phParTree
                  );

S_CloseTree() closes the tree, saves it on disk in the file it was created at or loaded from, and releases the tree handle. A saved tree can be further opened. The released tree handle cannot be used any more for accessing the tree.

S_COMPLETION_CODE S_SaveTree(
                    S_TREE_HANDLE * phParTree
                  );

S_SaveTree() saves the specified tree on disk in the file it was created at or loaded from, but doesn’t close the tree. After saving the tree remains accessible via the same tree handle. This function can be useful for temporary backups of the tree.

S_COMPLETION_CODE S_Search(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poParKey,
                    S_BOOL * pbIsFound
                  );

S_Search() performs searching in the specified tree for a specified key. As a result it forms the value of the specified Boolean parameter pbIsFound, which is S_TRUE if the key is found in the tree or S_FALSE otherwise, and returns a completion code.

S_COMPLETION_CODE S_Insert(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poParKey
                  );

S_Insert() inserts the given key to the specified tree, a completion code is returned.

S_COMPLETION_CODE S_Delete(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poParKey
                  );

S_Delete() deletes the given key from the specified tree, a completion code is returned.

S_COMPLETION_CODE S_First(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poResKey,
                    S_BOOL * pbIsFound
                  );

Since the set of keys stored in a S(B)-tree is linearly ordered, it is natural to be able to obtain the first, the last key in the set, the next, and the previous keys to a given one.

S_First() looks for the first key in the specified tree, and assigns the result to the output parameter poResKey. The output parameter pbIsFound is either S_TRUE if the tree is not empty, or S_FALSE otherwise.

S_COMPLETION_CODE S_Last(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poResKey,
                    S_BOOL * pbIsFound
                  );

S_Last() looks for the last key in the specified tree, and assigns the result to the output parameter poResKey. The output parameter pbIsFound is either S_TRUE if the tree is not empty, or S_FALSE otherwise.

S_COMPLETION_CODE S_Next(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poParKey,
                    S_KEY * poResKey,
                    S_BOOL * pbIsFound
                  );

S_Next() looks in the specified tree for the key next to the given key poParKey, and assigns the result to the output parameter poResKey. The output parameter pbIsFound is either S_TRUE if the next key exists in the tree, or S_FALSE otherwise.

Note that the given key poParKey shouldn’t necessarily be contained in the tree. To find the next means to find the minimal key in the tree that is greater than the given key.

S_COMPLETION_CODE S_Previous(
                    S_TREE_HANDLE hParTree,
                    S_KEY * poParKey,
                    S_KEY * poResKey,
                    S_BOOL * pbIsFound
                  );

S_Previous() looks in the specified tree for the key previous to the given key poParKey, and assigns the result to the output parameter poResKey. The output parameter pbIsFound is either S_TRUE if the previous key exists in the tree, or S_FALSE otherwise.

Note that the given key poParKey shouldn’t necessarily be contained in the tree. To find the previous means to find the maximal key in the tree that is less than the given key.

The rest of the functions return the specified tree parameters:

b, q, p, MuMax

and the tree intrinsic properties:

	Number of nodes in the tree
	Number of keys in the tree
	The tree total weight
	The tree height
	The tree utilization

Normally the return value of any of the functions is non-negative. A negative value is returned if the tree handle is invalid.

Here are the prototypes of the functions:

int S_TreeLocality(
        S_TREE_HANDLE hParTree
    );

int S_TreeOrder(
        S_TREE_HANDLE hParTree
    );

int S_TreeRank(
        S_TREE_HANDLE hParTree
    );

int S_TreeMaxKeyWeight(
        S_TREE_HANDLE hParTree
    );

long S_TreeNrNodes(
        S_TREE_HANDLE hParTree
    );

long S_TreeNrKeys(
        S_TREE_HANDLE hParTree
    );

long S_TreeWeight(
        S_TREE_HANDLE hParTree
    );

int S_TreeHeight(
        S_TREE_HANDLE hParTree
    );

double S_TreeUtilization(
        S_TREE_HANDLE hParTree
    );

Here is the list of completion codes with their value and short descriptions.