Menu
I have just read a paper on "in memory OLTP" for the next version of SQL server; it mentions BW-Tree as being added as well as hash indexes in CTP2.
So what is a BW-Tree? Can someone explain a bit about it without me (and everyone else) having to read a 12 page research paper.
898
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.
A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data. It is most commonly used in database and file systems.
Number of keys Hence, a B-tree with n keys has a height at most 1+ logb((n+1)/2). This means that search time is O(log n). B-trees are often used as representations for very large dictionaries. There are two main ways to store the items associated with each key: 1.
In a nutshell, a bw-tree is a kind of b-tree that is optimized for in-memory and for high concurrency.
For in-memory: the pages are variable-size and always tightly packed; there are no partially-filled pages
For high-concurrency: the data structure is completely latch- and lock-free to support concurrent DML without blocking.
78
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
