File: DBIndex.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Contents: Declarations of DBIndex level data types, and initialize/finalize procs.
Last edited by:
Suzuki on May 8, 1980 3:47 PM
Cattell on September 15, 1983 3:36 pm
MBrown on December 2, 1982 2:37 pm
Willie-Sue, February 15, 1985 11:22:43 am PST
Widom, September 4, 1985 8:59:35 pm PDT
Donahue, May 23, 1986 10:24:45 am PDT
DIRECTORY
DBCommon,
DBStorage,
DBStoragePage;
DBIndex: CEDAR DEFINITIONS = BEGIN
RealIndexHandle: TYPE = REF IndexObject;
IndexObject:
TYPE =
RECORD [
tid: DBCommon.TID,
segment: DBCommon.DBPage, -- segment in which the index lives
rootDB: DBCommon.DBPage, -- NullDBPage iff the index is empty
root: DBCommon.CacheHandle, -- always a hint
depth: CARDINAL, -- 0 if the index is empty
front, back: RealIndexHandle, -- for doubly linkded lists
free: BOOLEAN -- TRUE iff it does not point to real index
];
IndexKey: TYPE = LONG POINTER TO KeyBody;
KeyBody:
TYPE = DBCommon.KeyBody;
Page: TYPE = REF PageObject;
PageObject:
TYPE =
RECORD [
tree: RealIndexHandle,
db: DBCommon.DBPage,
cache: DBCommon.CacheHandle,
depth: CARDINAL, -- depth = 1 for leaf, >1 for non-leaf (0 for empty tree)
pointer: LONG POINTER TO Core, -- points to the cached page
free: BOOLEAN, -- so that this page object may be re-used
front: Page,
back: Page];
State: TYPE = {normal, split, merge, delete, deleteFromNextPage};
Core:
TYPE =
MACHINE
DEPENDENT
RECORD [
tag: DBStoragePage.PageHeader, -- =6 for Btree
left, right: DBCommon.DBPage,
size: CARDINAL,
index: ARRAY [0..CoreIndexSize) OF CARDINAL];
Core is the data structure of a Btree page. The index array is further divided as follows: The front part of index is ARRAY[0..size) OF CARDINAL, whose elements are indices of this array. They represent the start index of the i-th entry. The end part of index is the entries, which are allocated from the end. Each entry consists of two words of value and a Bstring. However, for internal nodes, the 0-th entry consists of only value.
ItemHandle: TYPE = LONG POINTER TO Item;
Item:
TYPE =
MACHINE
DEPENDENT
RECORD [
value: LONG CARDINAL,
length: CARDINAL,
text: PACKED ARRAY [0..0) OF CHARACTER];
Item is the internal object representing <key,value> pair.
Constants
OverHead: CARDINAL = 6;
FullPage: CARDINAL = DBCommon.WordsPerPage;
HalfPage: CARDINAL = FullPage/2 - 2;
CoreIndexSize: CARDINAL = FullPage - OverHead;
CallAfterFinishTransaction: PROC [s: DBCommon.Segment];
END.--DBIndex
CHANGE LOG
Created by Suzuki on May 8, 1980 3:49 PM
Created for use by DBStorage. They should be called by CreateDatabase, OpenDatabase, and CloseDatabase.
Re-created by Cattell on September 21, 1982 9:09 pm
Moved DBIndexInternal into here: its former log follows:
Changed halfPage from FullPage/2 to FullPage/2 - 2 to try to fix some boundary threshold problems on when to split and merge pages.
by Cattell: June 22, 1982 10:32 am
Changed RealIndexHandle and Page to be REFs.
by Cattell: August 6, 1982 2:17 pm
Changed by MBrown on December 2, 1982 2:35 pm
Eliminated Finalize, added CallAfterFinishTransaction.
Changed by MBrown on September 15, 1983 12:46 pm
Conversion to 5.0. IndexKeys may contains REFs to allocated storage, or pointers.
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting
Changed by Donahue on March 3, 1986 7:46:30 am PST
Changes to make Key Bodies visible through DBStorage interface