bnclabs / robt Goto Github PK

One of the advantage of using read-only immutable btree index is that caching the btree-blocks are very straight-forward. A typical requirement would be:

• Have an in-memory (key,value) map where key is file-position as u64 type and value is Vec<Entry<K,V,D>>. Note that we can as well cache parsed blocks.
• We cannot cache all blocks, to limit caching we do the following.
  • Cache all inter-mediate blocks upto N levels.
  • Cache all intermediate blocks, but not leaf-blocks.
• Now caching leaf-blocks would require an eviction strategy. We can handle that as a separate issue.

Get() operation into the index can be made faster by attaching a bloom-filter to the index. Typically it is expected to give false-positive by no false-negative. Bitmap index (implementing the Bloom) is already integrated with the index Builder type. We need to integrate them on the read-side. Specifically on the get() side.