Will MATREADs add speed?

B-TREE-P has been coded to use B-tree nodes that keep a key count in attribute one of the node, a multivalued list of physical keys in attribute two, a (sometimes null) multivalued list of node pointers in attribute three, and a parent node pointer in attribute four.

The BTPINS, BTPDEL, and BTPFIND routines use dynamic arrays to hold the B-tree nodes, and frequently perform a binary search on the list of keys in attribute two whenever a key needs to be looked up. Because dynamic array indexing is so much slower than dimensioned array indexing, it's a tempting idea to hold the B-tree nodes in dimensioned arrays in an attempt to gain some speed.

Unfortunately, our investigations have shown that trying to use dimensioned arrays is probably not worth the effort. If nodes are stored as dynamic arrays, but converted to dimensioned arrays for searching, the cost of conversion uses up any gain realized during searching. If nodes are stored as dimensioned arrays and accessed with MAT statements, conversion is unnecessary, but node layout is a bit more complicated, and the statements to insert or delete a key in a node become very messy.