ravi@maui.cs.ucla.edu (T.M Ravi) (03/17/90)
I remember seeing a bunch of messages a few months back about B/B+ trees. We already have the design of locking and transaction and buffer management worked out and are trying to design a traditional high performance index manager using B+ trees. I would welcome any information, papers or references on the implementation of an index manager. Particularly issues such as key compression, interface to the index manager, pre-allocation of pages etc. Thanks ravi ravi@cs.ucla.edu
trogers%yosemite@Sun.COM (Tom Rogers - Database Engineering) (03/20/90)
>I remember seeing a bunch of messages a few months back about B/B+ trees. >We already have the design of locking and transaction and buffer management >worked out and are trying to design a traditional high performance index >manager using B+ trees. > >I would welcome any information, papers or references on the implementation >of an index manager. Particularly issues such as key compression, interface >to the index manager, pre-allocation of pages etc. > >ravi@cs.ucla.edu You might be interested in looking into Sun's NetISAM. It is a super-set implementation of the X/Open Portability Guide 3 ISAM (Indexed Sequential Access Method), which is the only record manager standard for Unix today. NetISAM is really a B*-tree implementation (or B+ tree, or whatever you want to call it -- leaves of the tree hold just the index entries, not the data record). In addition to sequential, keyed, and indexed sequential lookup, it has enhancements for lookup by record number, a binary data type, and variable-length record support. It also has a client-server architecture for correct operation in a network of heterogeneous machines. The performance is especially impressive since we've measured thousands of operations per second locally and hundreds of operations (a single read, write, or update) per second over the network [your mileage will vary depending upon your application]. The performance is due to efficient internal design, use of memory-mapped i/o, ability to spawn multiple servers, and ability to link directly to access method routines avoiding talking to a daemon in the local case. Some articles on this product will be appearing soon. There are dbms texts like Wiederhold's that discuss access methods. If you are interested in looking at key compression, pick up a C-ISAM manual to see what it does, or look into VSAM's key compression, since it was one of the first access methods that did compression. As far as interfaces go, you should look at the XPG3 ISAM spec, and it is available from X/Open (the San Francisco office phone is 415-773-5383. They also have home offices in London, and probably an office on the east coast, USA). For more information on NetISAM, I'm sure you can contact your local Sun Sales Rep. You can also send email to kevinm@sun.com.