Apple Inc.

Murali Vemulapati

Frank Lu

James Qiu

Jonathan Thatcher

Carl Wang

Terrence Barwegen

Representative embodiments enable the management of index structures for data tables within a database. The techniques can include (1) receiving a request to perform an operation (e.g., read, write, etc.) on a row identifier (ID) associated with an index structure, (2) identifying a plurality of segments that corresponds to the index structure, where each segment stores a respective bitmap, (3) identifying, based on the row ID, a logical block ID of a logical block that encompasses the row ID, (4) utilizing the logical block ID to identify, among the plurality of segments, a subset of segments encompassed by the logical block, and (5) parsing each segment of the subset of segments to identify a respective bitmap that encompasses the row ID, and (6) in response to identifying the respective bitmap: performing an operation on a bitmap value that corresponds to the row ID.

Techniques for managing index structures for database tables

System, method, and computer program product key compression and cached-locking are described. A computer system can store database files or operating system files in a tree data structure. The system can store data or metadata as key-value pairs in nodes of the tree data structure. The keys in the key-value pairs can have a hierarchical structure, which may or may not correspond to the tree data structure. The system can compress the keys by reducing duplicated storage of shared portions of the keys. The system can use an index in a tree node to represent the hierarchical structure of the key-value pairs stored in that tree node. To access a value in a key-value pair, the system can identify the tree node to search, query the index in that tree node to locate the value, and then access the value at the indexed location.

Hierarchical data storage

When different types of shared resources need mutex protection, the shared resources can be organized into classes. Each class of shared resources can have multiple types of resources. A mutex pool can store multiple mutex objects, each mutex object corresponding to a class of resources. The mutex object can be used to protect each shared resource in the corresponding class.

Class-based mutex

Methods, program products, and systems for checkpoint based progressive backup are described. When a system receives a request to update a page of a storage device storing database files of a database, the system can update the page and replicate the updated page in a shadow page in a backup queue. The backup queue can store multiple shadow pages, where each updated page can correspond to at most a specified number of shadow pages in the queue. Each shadow page can be associated with a timestamp of a latest update. At pre-specified temporal checkpoints, the system can write the shadow pages in the queue to a backup file in the order of the timestamps. Upon receiving a restoration request, the system can restore the database to a state as of the time of the checkpoint using the backup file.

Growing community of inventors

Cupertino, CA, United States of America

Murali Vemulapati