Incremental bloom filter rebuild for b+ trees under multi-version concurrency control

A system comprising:

• one or more processors;
• a volatile memory;
• and
• a non-volatile memory storing computer program code that when executed on the processor causes execution across the one or more processors of a process operable to perform the operations of:
• processing an update to a search tree and updating statistics, the search tree storing information about one or more objects indexed by corresponding object keys;
• determining to rebuild a first Bloom filter based on the statistics, the first Bloom filter associated with the search tree;
• generating a second Bloom filter associated with the search tree;
• populating the second Bloom filter as part of a tracing garbage collection process;
• and
• replacing the first Bloom filter with the second Bloom filter.

A computer program product tangibly embodied in a non-transitory computer-readable medium, the computer-readable medium storing program instructions that are executable to:

• process an update to a search tree and update statistics, the search tree storing information about one or more objects indexed by corresponding object keys;
• determine to rebuild a first Bloom filter based on the statistics, the first Bloom filter associated with the search tree;
• generate a second Bloom filter associated with the search tree;
• populate the second Bloom filter as part of a tracing garbage collection process;
• and
• replace the first Bloom filter with the second Bloom filter.