The minimum node size is 2

The second argument to the BTPINS and BTPDEL subroutines is the node size, which can be a constant or variable. Branches #1 incorrectly states the node size can have any value from 1 up. Actually, the node size must be greater than 1, since BTPDEL will corrupt a B-tree if the node size equals 1.

Issues of Branches recommend node sizes from 5 to 50, depending on circumstances. For example, see the benchmarks mentioned in Branches #8. B-trees created with very small node sizes tend to be so deep that the average key access time begins to suffer and/or lots of disk space is consumed for node pointers, so requiring a node size greater than 1 is not a penalty. If you are trying to use a node size as small as 1 or 2, increasing the node size will improve the performance of your B-tree accesses and/or save disk space. Otherwise, you are probably indexing so few records that a B-tree is not really necessary.

Note that the general concept of B-trees doesn't prevent a node size of 1, it's just the actual way BTPDEL is coded that prevents the use of that node size. (That's because line 121 of BTPDEL assumes that a momentary key count of zero guarantees a root node is being manipulated, which is true when the node size is greater than 1, but which is possibly true for any node when the node size is 1.)

Although the FAST.BUILD program in Branches #6, like BTPINS, can correctly build a B-tree with node size 1, future BTPDEL calls can still corrupt the B-tree, so the expression SIZE<1 in line 7 of FAST.BUILD should be changed to SIZE<=1 to prevent B-trees of that type from being built. Ambitious users may also want to add code guaranteeing BTPDEL only accepts calls with a node size greater than 1, but that adds execution time overhead to every deletion.

Of course, B-TREE-P can even be changed to avoid the use of node sizes in subroutine calls altogether. When a B-tree is created, it's node size can be saved (in the B-tree itself, or in some other file or data structure, or even as part of the name of the B-tree), and BTPINS and BTPDEL can simply retrieve the saved node size for each B-tree as necessary, although this again tends to add overhead to the time required to manipulate a B-tree.

Our thanks to Dan Penny of Samuelson Associates for bringing this matter to our attention.