A BTree is a data structure for maintaining an ordered collection of objects (or entries) stored as a tree of fixed-size pages. The entries are each smaller than a page and are stored many per page; thus, each interior page of the tree has many branches, so even a very large tree is quite shallow (a depth of 3 or 4 is typical). This means that finding an arbitrary entry is relatively inexpensive in terms of the number of pages that must be accessed. The cost of an update is also reasonable and has an upper bound which is linear in the depth of the tree. Finally, the tree has very good locality, so references to consecutive entries usually access the same page.

For further information on the properties of BTrees in general, please read Knuth, The Art of Computer Programming, vol. 3, section 6.2.4.

This BTree package is a Cedar transliteration of one written in BCPL by Ed McCreight and used for maintaining the file directory in IFS. The important properties that distinguish it from existing Mesa BTree packages are:

It is intended that this package be suitable for use in maintaining any ordered data structure that must be stored externally, i.e., is either permanent or is (potentially) too large to keep in virtual memory. The most obvious application is a file directory. For smaller applications involving temporary data only, an internal data structure such as a RedBlackTree is more efficient to access and maintain.

The primary documentation for the BTree package is the interface BTree.mesa, obtained via BTree.df. The following is an overview of how the package is intended to be used; consult the interface itself for details.

The client must provide two sets of procedures, called the representation primitives and the storage primitives. The BTree package is object-oriented, i.e., a single instantiation of the package suffices to deal with an arbitrary number of Tree objects; and each Tree object instance can have an independent set of representation and storage primitives associated with it.

The representation primitives enable the package to find out everything it needs to know about BTree entries and keys. The most important are EntrySize, which gives the size of an entry in words, and Compare, which gives the result of comparing a key with an entry (less, equal, or greater). The package does not do anything with keys besides Compare them to entries. Additionally, there are procedures for converting between REF and LONG POINTER (i.e., safe and unsafe) references to entries.

The storage primitives are the means by which the package accesses the pages in which the BTree is stored. The package gains access to the contents of a page by calling the ReferencePage procedure, which returns a LONG POINTER to a block of virtual memory containing a copy of that page. When the package is finished with the page, it calls ReleasePage; subsequently, the page storage implementation may rewrite the page to permanent storage (if dirty) and reclaim the virtual memory.

The package comes in two parts. The main part, BTreeImpl.bcd, exports the BTree interface. Additionally, there is an example implementation of the page storage primitives called BTreeVMImpl, which exports the BTreeVM interface. This implementation is intended for building a temporary or permanent BTree on raw Cedar Nucleus files. It maintains a VM cache whose size is specified by the client; and it reads and writes the file explicitly, using File.Read and File.Write. BTree and BTreeVM are both exported from the BasicCedar boot file.

The idea is that the client program first calls BTreeVM.Open, passing a file capability and obtaining a storage handle and a set of storage primitives. These, along with the client's representation primitives, should then be passed to BTree.Open, which returns a Tree handle upon which BTree operations may be performed.

There is no explicit Close operation. The Tree and storage handles are collectible objects, which vanish when the last REFs to them disappear.

There also exists a separate package, BTreeSimple, intended for use by clients with unsophisticated needs. It makes some conventional assumptions about how the entries are interpreted (text keys, sequence values) and how the BTree is stored (an FS file). In return for this loss of flexibility, the BTreeSimple package takes care of providing the representation and storage primitives and does certain other bookkeeping that the basic BTree package requires the client to do. The implementation is BTreeSimpleImpl, which is not part of the boot file.

The performance of the BTree package depends on many variables: tree size, page size, access patterns, caching behavior of the storage primitives, and others. A few general statements about performance are offered here, followed by some measured results.

It is crucial that the storage implementation include a substantial amount of caching, managed in an LRU fashion. In many situations, the BTree package references a given page multiple times in the course of a single update. Even ignoring this, in most applications it is common for clients to make references to the same or closely-related entries over a short interval of time; the resulting locality of reference has a performance benefit only when redundant storage reads are avoided by use of a cache.

The size of the cache relative to the size of the BTree can have a substantial effect on performance, as the results below show. Additionally, it should be noted that for a large BTree it is desirable to have a large page size; given a reasonably large amount of space for a cache, it is better to have a modest number of relatively large pages than a larger number of small pages. This is because the main cost of performing an operation on a large BTree stored on a disk is disk access time (as opposed to transfer time); and larger pages mean more entries per page, a shallower tree, and fewer accesses per operation.

When updating a BTree, a tradeoff must be made between the desire for good performance and the desire to maintain a consistent permanent state of the tree. If it is desired that the permanent state be consistent between every update then more writes are required, thus reducing performance. The client program controls this tradeoff by use of the maintainRecomputableState argument of BTree.Open and the BTree.SetUpdateInProgress procedure. Of course, if consistency is being maintained at a lower level, e.g., by keeping the BTree in an Alpine file under a transaction, then no provisions need be made at the BTree level for maintaining consistency.

The measurements below were obtained using the BTreeTest tool, which is available as a separate package. This program uses BTreeVM to manage a BTree stored in a temporary file (which is deleted when the tool is destroyed). It obtains parameters from the user, randomly performs various operations on the tree, and displays a number of performance statistics.

Running BTreeTest from the UserExec opens a viewer containing a command menu, several user-adjustable parameters, and a table of results. The parameters are:

A test is started by clicking Start, and is ended by clicking Stop. The results are updated every few seconds while the test is running. Clicking InitTree resets the tree to empty before the beginning of a test. (It is necessary to do this after changing DiskPages/BTreePage or MaxTreeEntries.) ResetStats resets the statistics to zero but does not change the tree. The results are:

Here are some results, obtained on a Dorado. (These numbers are for Cedar 4, using Pilot file facilities. No complete set of corresponding measurements have yet been made for Cedar 5, though some preliminary tests demonstrated an improvement of about 30%.)

A few things are worth noting about these results. Test 1 uses a cache large enough to hold the entire tree and never writes any pages to permanent storage (except at the end of the test, where it isn't measured). This gives a good approximation of the CPU cost of operations performed on a 3-level BTree. As is evident from comparing test 1's results with the others, normally most of the time required for a BTree operation is spent waiting for the disk.

Test 2 is the same as test 1 except that the permanent state is written to storage at the end of every update. Tests 3 and 4 are similar to 1 and 2 except that the cache is much smaller than the tree, so many more reads and writes occur. Interestingly, the choice of whether or not to write storage after each update has only a modest effect on %R+W time in tests 3 and 4. This is presumably because most dirty pages get written anyway as a result of being displaced during later references to other parts of the tree. (The decrease in lookup time from test 3 to test 4 is a good indication that this is what is happening.)

Tests 5 through 7 are for a much larger BTree. Tests 6 and 7 show the effect of varying the page size, given a fixed-size cache. It is evident that the larger page size yields better performance in all respects.

The variations in time per read or write across all the tests are partially explainable as being related to the size of the tree (a larger tree means increased time spent seeking between different pages of it). Variations among tests with equal-size trees are probably Pilot artifacts.

Finally, it should be noted that the test program probes the BTree at random. Real applications may be expected to exhibit more locality in tree references, and consequently a higher hit rate and less time spent reading and writing storage.