A BTree contains an ordered set of Entries. From the BTree package's point of view, an Entry is simply an uninterpreted array of words. A Record is a collectible object containing a copy of an Entry. A Key identifies an Entry (or potential Entry) in the BTree; there is a one-to-one relationship between Keys and Entries. Each Entry contains (some encoding of) the information in the corresponding Key, such that it is possible to determine the ordering relation between any Key and any Entry. Also, each Entry typically contains additional information which is the "value" associated with the Key; but the BTree package has no cognizance of this. (An Entry will typically contain a copy of the Key that addresses it, but the package doesn't require that; a Key might contain, for example, auxiliary lookup information that makes Compare go faster.)

All knowledge of the representation of Entries, Records, and Keys is vested in the client program. Each client may have its own TYPEs defining the concrete representations of these objects. To permit the BTree package to be shared among all such clients without recompilation, this interface defines these objects in such a way that type checking is mostly bypassed. A cautious client will define a specialized BTree interface as a veneer over this one, exporting INLINE procedures which "translate" between the specific concrete types being used externally and the promiscuous ones defined here.

Tree: TYPE = REF TreeObject;

TreeObject: TYPE; -- This represents the volatile state of an open BTree

Entry: TYPE = LONG POINTER --TO READONLY EntryObject--;

EntryObject: TYPE;

Record: TYPE = REF ANY --RecordObject--;

RecordObject: TYPE;

Key: TYPE = REF ANY --KeyObject--;

KeyObject: TYPE;

Operations on client-provided objects

These operations are provided by the client when the tree is opened.

When an Entry is passed to a client-provided procedure, it is valid only until that procedure returns; the client must not store it in any variable whose lifetime exceeds that of the procedure call.

Comparison: TYPE = Basics.Comparison;

Compare: TYPE = UNSAFE PROCEDURE [key: Key, entry: Entry] RETURNS [Comparison];

CompareEntries: TYPE = UNSAFE PROCEDURE [entry1, entry2: Entry] RETURNS [Comparison];

EntSize: TYPE = [0..LAST[PageSize]];

EntrySize: TYPE = UNSAFE PROCEDURE [entry: Entry] RETURNS [words: EntSize];

reservedWordsPerPage: CARDINAL = 3;

EntryFromRecord: TYPE = UNSAFE PROCEDURE [record: Record] RETURNS [entry: Entry];

NewRecordFromEntry: TYPE = UNSAFE PROCEDURE [entry: Entry] RETURNS [record: Record];

RepresentationPrimitives: TYPE = RECORD [

The permanent storage for a BTree is represented by a client-provided PageStorage object; BTree pages are stored in an array of "pages" numbered [0..LAST[PageNumber]] relative to that object. Each page is typically the underlying physical page size (e.g., File.wordsPerPage) or some multiple thereof; PageSize defines the "reasonable" range of page sizes, within which one may expect the BTree package to operate with reasonable performance.

The ratio of page size to average entry size, times about .75, defines a tree's "branching factor", i.e., the number of descendants of each non-leaf page. A branching factor of about 7 should be considered the minimum acceptable (this gives you about 400 entries in a 3-level tree); much larger branching factors (10 to 25) are preferable. (Actually, with a uniform distribution of variable-size entries, the BTree package achieves a higher branching factor than the ratio given above, because it endeavors to keep smaller keys in the non-leaf pages).

The BTree package uses lower-numbered pages first. Precisely, when the package references page i for the first time, it is because all pages in [0..i) are in use and a new page is required. However, at any given time, the interval of in-use pages may be sparse.

The page storage is assumed to behave much like a virtual memory in which the Mesa VM is the "real" memory and the page storage array is the "virtual" memory. That is, the BTree package makes an explicit read or write reference with a "virtual" address which is a PageNumber and obtains a LONG POINTER to a page in the Mesa VM either mapped onto or containing a copy of that storage page. This LONG POINTER must remain valid until explicitly released by the BTree package. Any time after it is released, the Mesa VM page may be rewritten to the storage page (if dirty) and then reclaimed.

The page storage is expected to include a substantial amount of caching. That is, if a given PageNumber was referenced and released recently, a new reference to that PageNumber is expected to have very low cost on the average. In the same vein, instant rewriting of dirty pages upon their release is not recommended; systematic rewriting (if desired) should be deferred until the end of an operation. The cache should have room for at least log to the base branching-factor of the number of entries (i.e., the number of levels in the tree) so that all the pages in the lookup path to an entry will fit at once. A cache size at least several times this is recommended, because updates typically touch more pages than lookups do. (Precisely, a lookup references precisely one page per level, and an update references at most three pages per level.)

During any single BTree operation, the BTree package promises never to have more than 3 simultaneous references in progress; these may include multiple references to the same PageNumber. There are no references in progress between BTree operations.

PageStorage: TYPE = REF ANY --PageStorageObject--;

PageStorageObject: TYPE;

PageNumber: TYPE = CARDINAL;

statePage: PageNumber = 0;

PageSize: TYPE = [0 .. 16*File.wordsPerPage]; -- actually [File.wordsPerPage .. ...], but the damned compiler uses an offset representation if I say that

PagePtr: TYPE = LONG POINTER --TO ARRAY [0..pageSize) OF WORD--;

ReferenceType: TYPE = {read, write, new};

UpdateState: TYPE = {startOfUpdate, endOfUpdate, unchanged};

Operations on page storage

ReferencePage: TYPE = UNSAFE PROCEDURE [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr];

ReleasePage: TYPE = UNSAFE PROCEDURE [storage: PageStorage, number: PageNumber, update: UpdateState ← unchanged];

PageStoragePrimitives: TYPE = RECORD [

State: TYPE = {closed, suspended, open};

New: PROCEDURE [repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives, minEntrySize: CARDINAL ← 1, initialState: State[closed..suspended] ← closed] RETURNS [tree: Tree];

Open: PROCEDURE [tree: Tree, storage: PageStorage, pageSize: PageSize ← File.wordsPerPage, initialize: BOOLEAN ← FALSE, maintainRecomputableState: BOOLEAN ← TRUE];

SetState: PROCEDURE [tree: Tree, state: State[closed..suspended]];

GetState: PROCEDURE [tree: Tree] RETURNS [state: State, entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL, storage: PageStorage];

Validate: PROCEDURE [tree: Tree];

SetUpdateInProgress: PROCEDURE [tree: Tree, updateInProgress: BOOLEAN];

There are two classes of BTree access operations. The higher-level operations traffic exclusively in REFs and are SAFE in the Cedar sense. In general, each BTree access involves the creation of a new Record object. Thus, the higher-level operations are good for isolated accesses, but not for applications requiring good performance such as exhaustive enumerations.

Corresponding to each of the higher-level operations there is a lower-level UNSAFE operation which does not require allocating any new Records. These are defined in the next section.

Relation: TYPE = {less, lessEqual, equal, greaterEqual, greater};

ReadRecord: PROCEDURE [tree: Tree, key: Key, relation: Relation ← equal, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE] RETURNS [record: Record];

EnumerateRecords: PROCEDURE [tree: Tree, key: Key, relation: Relation ← equal, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: PROCEDURE [record: Record] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN];

UpdateType: TYPE = {insert, replace, insertOrReplace};

UpdateRecord: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, record: Record, updateType: UpdateType ← insertOrReplace];

DeleteKey: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE] RETURNS [found: BOOLEAN];

These are all UNSAFE, but more efficient than the corresponding SAFE procedures since no storage allocation is required.

ReadEntry: UNSAFE PROCEDURE [tree: Tree, key: Key, relation: Relation ← equal, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]];

EnumerateEntries: UNSAFE PROCEDURE [tree: Tree, key: Key, relation: Relation ← equal, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN];

UpdateEntry: UNSAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, words: EntSize, Proc: UNSAFE PROCEDURE [entry: Entry], updateType: UpdateType ← insertOrReplace];

SalvageEntries: UNSAFE PROCEDURE [tree: Tree, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN];

All procedures that look up keys accept optional PathStk and useExistingPath arguments. If a PathStk is supplied then the operation fills it in with the path to the BTree entry that was located (the last such entry in the case of an enumeration). If useExistingPath=TRUE (in which case the PathStk must not be NIL or Error[nilPathStk] will be raised) then the BTree package will attempt to access the entry described by the PathStk; only if the entry is incorrect or the PathStk is otherwise invalid will a new path be constructed. Use of PathStk hints can substantially speed up certain operations such as repeated Reads, resuming a suspended Enumerate, or performing an Update of an entry that was just looked up.

It would be illegal for the same PathStk to be used in multiple concurrent calls to BTree package procedures; no check is made for this.

PathStk: TYPE = REF PathStkObject;

PathStkObject: TYPE;

NewPathStk: PROCEDURE RETURNS [pathStk: PathStk];

Error: ERROR [reason: Reason];

Reason: TYPE = {badSeal, closed, depthExceeded, entriesOutOfOrder, entrySizesWrong, nilPathStk, other, wrongEntryProduced, wrongPageSize, wrongUpdateType};

UpdateInProgress: SIGNAL;

This package can accomodate two rather different approaches for maintaining consistency in the face of concurrent access and crashes in mid-update. These are distinguished by whether or not accesses to the underlying page storage are covered by a transaction which includes locking, e.g., an Alpine transaction. It is required that all clients agree on which approach is being used for any given BTree.

If transactions are not being used, it is required that at most one Tree handle be active for a given BTree (i.e., a given set of underlying PageStorage pages). For this case, the BTree package internally locks the entire Tree during every operation, enforcing a conventional "readers and writers" discipline (any number of simultaneous readers or exactly one writer, but not both).

If transactions are being used, clients may access a BTree with different Tree handles, so long as the PageStorage accesses performed for each one are covered by a different transaction. In this case, the BTree package's locking mechanism is subverted, but consistency is assured by the page locking that occurs as part of the PageStorage references. This permits increased concurrency at the risk of possible deadlocks. (With Alpine, maximum concurrency is obtained by covering write references with "update" as opposed to "write" locks so as not to block concurrent reads.) Note that it is still permissible for multiple clients to use the same Tree handle concurrently (i.e., under the same transaction), since the internal Tree lock is still in effect and keeps the clients out of each others' way.

The top-level permanent state of the BTree is kept in the statePage. Besides vital information such as the PageNumber of the root of the tree, the statePage optionally holds two pieces of recomputable information: the (approximate) number of entries in the BTree, and an "update in progress" flag which is set at the beginning of an update, cleared at the end, and checked during Open. Whether or not these two fields are maintained is controlled by the maintainRecomputableState argument of Open.

If the PageStorage accesses are not performed under a transaction, the "update in progress" flag may be used as a reliable indication of the consistency of the BTree if the PageStorage writes are managed in the following way. When the BTree package makes a (write) reference to the statePage and releases it with update=startOfUpdate, the statePage should be immediately rewritten to permanent storage. When the BTree package makes a (write) reference to the statePage and releases it with update=endOfUpdate, all dirty pages other than the statePage should be rewritten to permanent storage, followed by the statePage itself. (It is ok for the PageStorage implementation to write dirty pages at other times as well, except when references are in progress to them.) Note that updates are bracketed by statePage writes in this fashion only if maintainRecomputableState is TRUE. When the BTree package makes a (write) reference to a page other than the statePage and releases it with update=endOfUpdate, the update consists of that single write, so the tree is consistent both before and after the page is rewritten to permanent storage. Therefore, single-page updates are not bracketed with statePage writes. (This is why the permanent value of the entryCount is only approximate.)

If accesses are performed under a transaction, maintaining the recomputable state is inappropriate because doing so would result in a write lock being set on the statePage during every update, thereby reducing concurrency (only one transaction that updates the BTree could be in progress at a time). Therefore, maintainRecomputableState should be FALSE when operating in this fashion.

If the PageStorage primitives stop performing accesses under one transaction and begin using another transaction (e.g., because the client has finished the first transaction and started a new one), the ReOpen procedure should be called to inform the BTree package that any state it has cached in the Tree object (or associated PathStk objects) is no longer valid and must be re-read from the PageStorage. This is logically equivalent to creating a new Tree object, but is less costly. Note that the PageStorage cache must also be flushed so that subsequent references will give rise to real storage accesses that set locks under the new transaction.