* Performance of Binary Sort Access Method [BSAM] ( was Re: btrees)
[not found] <4jmnde$kv9@ruby.interactive.net>
@ 1996-04-01 0:00 ` The Right Reverend Colin James III
0 siblings, 0 replies; only message in thread
From: The Right Reverend Colin James III @ 1996-04-01 0:00 UTC (permalink / raw)
Performance statistics for the Binary Sort Access Method [BSAM],
US patent pending
Copyright 1996, Colin James III, All Rights Reserved
CEC Services, LLC, 2080 Kipling St, Lakewood, CO 80215-1502
Voice: 303.231.9437; Facsimile: 303.231.9438;
Email: cjames@cec-services.com
Abstract
========
The Binary Sort Access Method [BSAM], US patent pending, was tested
against B-tree for speed of adding keys in the same respective random
order into persistent data structures built from scratch, ie, not
inserted into pre-existing data structures.
BSAM added random keys on average of about 45% faster than B-tree.
BSAM retrieved a sorted list of keys on average about one magnitude
(10-times) faster than B-tree.
BSAM required about 2.3-times more disk space than did B-tree.
Test results
============
Number of unique keys (x 1000) added in the same random
order to respective data structures built from scratch
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
10 20 30 40 50 60 70 80 90 100 110
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
o : BSAM 175 399 561 813 971 1154 1470 1641 1816 2231 2425
x : B-tree 239 526 826 1150 1428 1774 2075 2407 - - -
-------------------------------------------------------
Time in seconds for each test
110 - o
100 - o
90 - o
80 - o x
70 - o x
60 - o x
50 - o x
40 - o x
30 - o x
20 - o x
10 - ox
0 + ------------------------------------------------
1 3 5 7 9 11 13 15 17 19 21 23
2 4 6 8 10 12 14 16 18 20 22 24
Description of BSAM
===================
This is proprietary because of US patent pending status. However,
potential licensees may qualify for information under a non disclosure
agreement available from the author above.
Description of BSAM test implementation
=======================================
BSAM was implemented in True BASIC Professional v 4.01. All movement
of keys was performed by hard disk access in real time as the data
base was assumed to be fully persistent.
Description of B-tree
=====================
The B-tree variation used is best examined first hand by the reader in
the True BASIC documentation in Chapter 48, The TB-Tree Library, and
in the source code which is included in the distribution. This
particular B-tree variation is remarkably efficient and hence
exceptionally fast, much more so in fact than that supplied with other
vendors' compilers which we own. The high quality of the TB-Tree
Library attests to the fact that professional mathematicians designed
and implemented it.
Description of B-tree implementation
====================================
Only two calls were used: BTOpen to open the database file; and Add
to insert the keys in 8-byte in IEEE number format.
Random key generation
=====================
The random keys to be added were unique for the range of keys. For
example, if 100,000 keys were required then 100,000 unique keys were
randomly generated in the numeric range of 1 to 100,000 such that no
key was used more than once. The random number function was seeded
identically for all runs such that the same series of random numbers
was generated for 1 to the numeric limit. True BASIC has an excellent
mathematical implementation of a pseudo random number generator [RNG].
To test the quality of the RNG, we randomly turned on pixels and
noticed no streaking line patterns. (We have found that this is a good
test of RNGs in two-dimensions, as supplied with other compilers.)
Acknowledgments
===============
Trademarks are hereby acknowledged by their respective holders.
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Colin James III, Principal Scientist cjames@cec-services.com
CEC Services, 2080 Kipling St, Lakewood, CO 80215-1502 USA
Voice: 303.231.9437; Facsimile: .231.9438
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
^ permalink raw reply [flat|nested] only message in thread