Relay-Version: version Notes 2.6.8 86/05/15 (HP beta); site wdl1.UUCP
From: smj@ssl-macc.co.uk (Steve Jefferson)
Date: Tue, 19 Aug 86 02:51:17 PDT
Date-Received: Fri, 22 Aug 86 00:29:46 PDT
Subject: B-tree code in C
Message-ID: <359@ssl-macc.co.uk>
Path: wdl1!sun!decwrl!amdcad!amd!intelca!qantel!lll-lcc!lll-crg!seismo!mcvax!ukc!dcl-cs!sslvax!smj
Newsgroups: net.sources
Distribution: net.sources
Reply-To: smj@sslvax.UUCP (Steve Jefferson)
Keywords: B-tree
Lines: 2574

This article consists of a set of C sources to implement a B-tree
algorithm and several accompanying tests. It was derived from a single 
program obtained from net.sources some time ago but has been revised and
extended somewhat since then. 

The code builds to 2 executables:
(1) btree.fe	- an interactive front-end to the main B-tree system
		  this implements a simple set of commands
		  <number>	: insert given key value into the tree
		  i<number>	: ditto
		  d<number>	: delete given key value from tree
		  l<number>	: locate a given key in tree
		  p		: print current tree
		  s		: set up a default tree
		  x		: exit from program
(2) btree.test	- a series of tests for the B-tree system - typically this
		  should be run after any significant change to the B-tree
		  code. 
		- 3 tests are performed as follows (a test will only
		  proceed if the previous test succeeded):
			(i)   Perform a series of random inserts, deletes
			      and searches, maintaining an external checklist 
			      and checking the shape of the tree after every
			      action
			(ii)  Insert a fixed number of keys in ascending order
			      then delete them in ascending order
			(iii) As (ii) but everything is in descending order

Limitations:
	(1)	The B-tree is implemented as a series of *struct*s in
		memory - explicit reads and writes of (disc) blocks would
		be more useful.
	(2)	The current system only allows for unique key values
		and not data with identical key values which can then be
		distinguished by the actual information content of the data.

If anyone has any suggestions or modifications for this code, or indeed has 
any B-tree code of their own which they are willing to release, I would most 
interested.

				Steve Jefferson
			(smj@uk.co.ssl-macc or smj@sslvax.UUCP)