Invention Grant
- Patent Title: Enhanced B-trees with record merging
- Patent Title (中): 增强的B树与记录合并
-
Application No.: US13630206Application Date: 2012-09-28
-
Publication No.: US09053140B2Publication Date: 2015-06-09
- Inventor: Wenguang Wang , David A. Majnemer
- Applicant: Apple Inc.
- Applicant Address: US CA Cupertino
- Assignee: Apple Inc.
- Current Assignee: Apple Inc.
- Current Assignee Address: US CA Cupertino
- Agency: Fish & Richardson P.C.
- Main IPC: G06F17/30
- IPC: G06F17/30

Abstract:
In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.
Public/Granted literature
- US20130204902A1 Enhanced B-Trees with Record Merging Public/Granted day:2013-08-08
Information query