Performance of Binary Sort Access Method [BSAM] ( was Re: btrees)

Performance of Binary Sort Access Method [BSAM] ( was Re: btrees)

[The Right Reverend Colin James III]

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 
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~