Seek (B+ tree) vs. Transfer(LSM tree) - Mac Track - 博客频道 - CSDN.NET

Seek (B+ tree) vs. Transfer(LSM tree) - Mac Track - 博客频道 - CSDN.NET

B+ trees

B+ trees have some specific features that allow for efficient insertion, lookup, and deletion of records that are identified by keys. They represent dynamic, multilevel indexes with lower and upper bounds as far as the number of keys in each segment (also called page) is concerned. Using these segments, they achieve a much higher fanout compared to binary trees, resulting in a much lower number of IO operations to find a specific key.

In addition, they also enable you to do range scans very efficiently, since the leaf nodes in the tree are linked and represent an in-order list of all keys, avoiding more costly tree traversals. That is one of the reasons why they are used for indexes in relational database systems.

In a B+ tree index, you get locality on a page-level (where page is synonymous to "block" in other systems): for example, the leaf pages look something like:

Read full article from Seek (B+ tree) vs. Transfer(LSM tree) - Mac Track - 博客频道 - CSDN.NET