From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,434c42804a3ca269,start X-Google-Attributes: gid103376,public From: cjames@melchizedek.cec-services.com (The Right Reverend Colin James III) Subject: Performance of Binary Sort Access Method [BSAM] ( was Re: btrees) Date: 1996/04/01 Message-ID: <315f78fd.376475833@news.dimensional.com> X-Deja-AN: 145184789 references: <4jmnde$kv9@ruby.interactive.net> organization: CEC Services, LLC reply-to: cjames@melchizedek.cec-services.com newsgroups: comp.lang.ada Date: 1996-04-01T00:00:00+00:00 List-Id: 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 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~