Querying a cascading index that avoids disk accesses
US8595248B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 20, 2009 |
| Grant date | Nov 26, 2013 |
| Priority date | — |
| Expiry date | Jan 27, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques for maintaining a cascading index are provided. In one approach, one or more branch node compression techniques are applied to the main index of a cascading index. In an approach, a Bloom filter is generated and associated with, e.g., a branch node in the main index. The Bloom filter is used to determine whether, without accessing any leaf blocks, a particular key value exists, e.g., in leaf blocks associated with the branch node. In an approach, a new redo record is generated in response to a merge operation between two levels of the cascading index. The new redo record comprises (a) one or more addresses of blocks that are affected by the merge operation, (b) data is that being “pushed down” to a lower level of the cascading index, and (c) one or more addresses of blocks that are written to disk storage as a result of the merge operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.