BW-Tree
A latch-free B-tree variant index structure proposed by David Lomet's team at Microsoft Research. It uses delta updates and mapping-table indirection to achieve high-concurrency, latch-free access, and serves as the core index component of the Hekaton in-memory database engine.
Timeline (last 90 days)
BW-Tree is a lock-free index tree work led by David Lomet's team at Microsoft.
Microsoft's in-memory database system Hekaton adopts lock-free technology and uses the BW-Tree provided by Lomet's team.
BW-Tree avoids the ABA problem through indirect addressing via a Mapping Table; the CAS operation targets the slot pointer in the mapping table, and pages themselves are never modified in place.
BW-Tree's Delta updates use CAS to point the mapping table pointer to a delta modification node, which has extremely low construction cost, but causes reads to require linear traversal of the Delta chain, hurting read performance.
BW-Tree periodically consolidates Deltas with the base page to rebuild a read-optimized consolidated page; the consolidation itself is also lock-free, accomplished via CAS.
BW-Tree uses an epoch mechanism to manage memory allocation and reclamation, ensuring that old states are not reclaimed before any thread has stopped referencing them.
All Facts (6)
BW-Tree is a lock-free index tree work led by David Lomet's team at Microsoft.
50%UnverifiedMicrosoft's in-memory database system Hekaton adopts lock-free technology and uses the BW-Tree provided by Lomet's team.
50%UnverifiedBW-Tree avoids the ABA problem through indirect addressing via a Mapping Table; the CAS operation targets the slot pointer in the mapping table, and pages themselves are never modified in place.
50%UnverifiedBW-Tree's Delta updates use CAS to point the mapping table pointer to a delta modification node, which has extremely low construction cost, but causes reads to require linear traversal of the Delta chain, hurting read performance.
50%UnverifiedBW-Tree periodically consolidates Deltas with the base page to rebuild a read-optimized consolidated page; the consolidation itself is also lock-free, accomplished via CAS.
50%UnverifiedBW-Tree uses an epoch mechanism to manage memory allocation and reclamation, ensuring that old states are not reclaimed before any thread has stopped referencing them.
50%