Importance

Loading Importance Indicators...

Abstract

A novel B tree data structure is taught and implemented for use in conjunction with a tertiary storage system. The tertiary storage system utilizes three levels of memory hierarchy: primary memory, such as RAM; read-write secondary storage, such as disk memory; and lower speed, and less expensive mass storage, for example a CD-ROM. A novel B tree is utilized to access data stored in two or more types of memory, such as a CD-ROM memory and a disk drive memory, and adapts for the provision of updated data stored on the hard disk which either replaces or supplements data stored on the CD-ROM. The B tree includes, for each data bucket, a pointer for both a CD-ROM and a disk drive location, and are, in certain embodiments, used in conjunction with a bit mask to indicate the presence of valid data in a first one of the memories, such as CD-ROM, and, if desired, a bloom filter associated with data stored in the second memory type, such as a magnetic disk, in order to speed accesses. The B tree of this invention is capable of being split, as needed, when entries are inserted into memory.

Loading the Abstract Image...

First Claim