How to delete one tree in a "forest"

If you decide to keep a number of B-trees all in the same file, you may eventually need to completely delete one B-tree without disturbing the other B-trees. There are a number of different ways to do this.

One way to delete a B-tree is to do an "unbuild". That is, use a small program similar to BUILD to read every item in the data file, but delete its entry in the B-tree. For example:

001 OPEN "B-TREE" TO BFILE ELSE STOP
002 OPEN "NAMES" TO NFILE ELSE STOP
003 SELECT NFILE
004 100 READNEXT ID ELSE STOP
005 READ ITEM FROM NFILE,ID ELSE GOTO 100
006 CALL BTPDEL("ZIP",5,BFILE,NFILE,ID,ITEM)
007 GO TO 100
008 END

The above program leaves behind an "empty" B-tree consisting of only an empty root node and the root pointer item named ZIP.

If the data file (NAMES in the above example) has already been destroyed and isn't available for running an unbuild, or if an unbuild runs too slowly, the B-tree can still be deleted by finding the names of all B-tree nodes and then deleting the B-tree node by node. You can use BTPSEQ to find the names of all B-tree nodes, if you know which node contains the first key stored at the start of the B-tree. The first key in a B-tree is the leftmost key in the leftmost node of the B-tree.

To find the leftmost node in a B-tree, start with the root node pointed to by the B-tree name item. If that node has pointers to other nodes, follow the leftmost pointer until a "leaf" node with no pointers is found. For example, if the B-tree root pointer item is called ZIP, and the ZIP item in the B-tree file contains the node number 305, then examine item 305. If attribute 3 of node 305 is empty, then you've found the leftmost node in the B-tree. If attribute 3 is not empty, the first value in that attribute is the number of the next-level node in which to repeat the search down the B-tree. Keep following the leftmost node numbers stored in attribute 3 until a leaf node with no more pointers is reached.

Once you know the number of the leftmost node in a B-tree, BTPSEQ can be used to identify all other nodes in the B-tree. The node numbers can be saved in a scratch file, collected in a SELECT list, and then deleted from the B-TREE file. For example, assume node 522 was found to be the leftmost node of a B-tree named ZIP, which is to be deleted. The following program will quickly save all of the B-tree's node numbers in a file called SCRATCH, without using the data file indexed by the B-tree:

001 OPEN "B-TREE" TO BFILE ELSE STOP
002 OPEN "SCRATCH" TO SFILE ELSE STOP
003 NODE = 522 ; POS = 1 ; ID = ""
004 LOOP
005  WRITE "" ON SFILE, NODE
006  CALL BTPSEQ(BFILE,NODE,POS,"NEXT",ID)
007 UNTIL ID = "" DO REPEAT
008 STOP
009 END

After running the above program, the command SELECT SCRATCH will collect all node numbers into a SELECT list, and the Editor or a delete utility can then be used to delete the nodes from the B-TREE file. Don't forget to also delete the root pointer item (named ZIP in the above discussion). Also, don't try to delete a node immediately after its number is returned by BTPSEQ. That's because BTPSEQ still needs the node and will repeatedly return the same node number (and occasionally the number of any children nodes) until POS has gone from 1 to the number of keys in the node.

Note that with a slightly more complicated version of the above program, any node (such as the root node) can be used to find all other nodes in a B-tree, without first having to determine the leftmost node: just call BTPSEQ repeatedly with "NEXT" to find all following node numbers, and call BTPSEQ repeatedly with "PREV" to find all preceding node numbers.

If the keys in the B-tree to be deleted are all noticeably different from the keys in all other B-trees in the file, then only a SELECT is necessary to find all nodes. For example, if all the keys contain a hyphen, and no other B-tree keys use hyphens, then use a command like SELECT B-TREE WITH AMC2 = "[-]" to get the same effect as a SELECT SCRATCH.