• A
    Modify FragmentedRangeTombstoneList member layout (#4632) · 6bee36a7
    Abhishek Madan 提交于
    Summary:
    Rather than storing a `vector<RangeTombstone>`, we now store a
    `vector<RangeTombstoneStack>` and a `vector<SequenceNumber>`. A
    `RangeTombstoneStack` contains the start and end keys of a range tombstone
    fragment, and indices into the seqnum vector to indicate which sequence
    numbers the fragment is located at. The diagram below illustrates an
    example:
    
    ```
    tombstones_:     [a, b) [c, e) [h, k)
                       | \   /  \   /  |
                       |  \ /    \ /   |
                       v   v      v    v
    tombstone_seqs_: [ 5 3 10 7 2 8 6  ]
    ```
    
    This format allows binary searching the tombstone list to use less key
    comparisons, which helps in cases where there are many overlapping
    tombstones. Also, this format makes it easier to add DBIter-like
    semantics to `FragmentedRangeTombstoneIterator` in the future.
    Pull Request resolved: https://github.com/facebook/rocksdb/pull/4632
    
    Differential Revision: D13053103
    
    Pulled By: abhimadan
    
    fbshipit-source-id: e8220cc712fcf5be4d602913bb23ace8ea5f8ef0
    6bee36a7
table_cache.cc 17.5 KB