AVLtree

-------------------------------------------------------------------------
FILES

	README		this file

	Makefile	makes the library and benchmark programs

	avltree.c	all the source code
	avltree.h	apps include this
	avltree.3	man page; installed as .gz

	test.c		example program from the man page

	avl_bench.c	a crude benchmark program

	db_avl.c	file for building a DB benchmark

	bplus.h		files for building a BPLUS benchmark
	fscompat.h
	bp_avl.c
			
-------------------------------------------------------------------------
DESCRIPTION

AVLtree is a small, malloc-based, in-memory index package generally 
like B-trees and hash tables.

The interface resembles that of the BPLUS (B-tree) index package.

Index creation options are:

  - fixed-length binary keys OR variable-length string keys
  - unique OR duplicate keys
  - with duplicate keys: 
      standard (void *) pointers for each key OR 
      instance-counting (saves time and memory)

Key insert/search time is O(log N).  References:

Adelson-Velskii, G. M., and E. M. Landis. 
  "An Algorithm for the Organization of Information." 
  Soviet Math. Doclady 3, 1962, pp. 1259-1263.
Knuth, D. E. 
  The Art of Computer Programming, Volume 3: Sorting and Searching 
  (2nd printing).  Addison-Wesley, 1975, pp. 451-468.

AVLtree was written by Gregory Tseytin, tseyting@acm.org.
Port-ified by Bill Ross, bross@nas.nasa.gov and ross@cgl.ucsf.edu.

-------------------------------------------------------------------------
BENCHMARKS

Some crude benchmarks run on freebsd AMD K6-2/333, 128M

	'db' cache allocation

db/a    16777216
db/b    65536
db/c    0

	bplus NUM_BUFS (bufsize 1024)

bp/a 	2048
bp/b	1024
bp/c	16

-- nkeys 10000    maxkeylen 20

avl    0.236u 0.000s 0:00.23 100.0%    10+666k    0+0io           0pf+0w

db/a   0.397u 0.015s 0:00.47 85.1%      5+1159k   0+0io           0pf+0w
db/b   0.446u 0.657s 0:01.12 97.3%      5+448k    0+5io           0pf+0w
db/c   0.571u 1.034s 0:01.63 98.1%      5+281k    1+1io           0pf+0w

bp/a   6.936u 1.106s 0:08.29 96.8%     20+2981k   0+1io           0pf+0w
bp/b   0.702u 1.030s 0:01.87 92.5%     20+287k    0+1io           0pf+0w
bp/c   0.766u 1.006s 0:01.90 92.6%     21+297k    0+1io           0pf+0w

-- nkeys 100000   maxkeylen 20

avl    2.782u  0.062s 0:02.89 98.2%    10+4258k   0+0io           0pf+0w

db/a   6.691u  0.101s 0:06.96 97.5%     5+8528k   4+0io           2pf+0w
db/b   6.775u 15.110s 0:25.70 85.1%     5+445k    0+8646io        0pf+0w
db/c   6.131u 20.912s 0:31.04 87.1%     5+283k    0+8781io        0pf+0w

bp/a 149.993u 21.840s 3:21.23 85.3%    20+2953k   0+7197io        0pf+0w
bp/b   9.105u 20.146s 0:34.38 85.0%    20+287k    0+7508io        0pf+0w
bp/c   8.716u 18.052s 0:31.73 84.3%    20+289k    0+7481io        0pf+0w 

-- nkeys 1000000  maxkeylen 20

avl   33.358u   1.039s  0:35.80 96.0%  10+39161k  0+0io           0pf+0w

db/a 286.446u 150.992s  9:45.73 74.6%   5+41877k  503123+265612io 1pf+0w
db/b 100.941u 462.011s 13:25.85 69.8%   5+444k    438767+827731io 1pf+0w
db/c  96.035u 510.166s 13:47.39 73.2%   5+283k    331206+842546io 0pf+0w

bp/a  [killed after 30 min]
bp/b 134.020u 481.339s 16:45.47 61.2%   20+288k   412025+756312io 2pf+0w
bp/c 119.542u 467.977s 16:13.10 60.3%   20+289k   496426+755972io 0pf+0w 

-------------------------------------------------------------------------