14.12

What trade offs do buffer trees pose as compared to LSM trees?


The idea of buffer trees can be used with any tree-structured index to reduce the cost of inserts and updates, including spatial indices. In contrast, LSM trees can only be used with linearly ordered data that are amenable to merging. On the other hand, buffer trees require more random I/O to perform insert operations as compared to (all variants of) LSM trees.

Write-optimized indices can significantly reduce the cost of inserts, and to a lesser extent, of updates, as compared to B+-trees. On the other hand, the index lookup cost can be significantly higher for write-optimized indices as compared to B+-trees.