Re: LSM tree for Postgres

ср, 5 авг. 2020 г., 09:13 Konstantin Knizhnik <k(dot)knizhnik(at)postgrespro(dot)ru>:
> Concerning degrade of basic index - B-Tree itself is balanced tree. Yes,
> insertion of random keys can cause split of B-Tree page.
> In the worst case half of B-Tree page will be empty. So B-Tree size will
> be two times larger than ideal tree.
> It may cause degrade up to two times. But that is all. There should not
> be infinite degrade of speed tending to zero.

My concerns are not just about space utilization. My main concern is
about the order of the pages. After the first merge the base index
will be filled in key order. So physical page ordering perfectly
matches their logical ordering. After the second merge some pages of
base index splits, and new pages are added to the end of the index.
Splits also happen in key order. So, now physical and logical
orderings match within two extents corresponding to first and second
merges, but not within the whole tree. While there are only few such
extents, disk page reads may in fact be mostly sequential, thanks to
OS cache and readahead. But finally, after many merges, we can end up
with mostly random page reads. For instance, leveldb doesn't have a
problem of ordering degradation, because it stores levels in sorted
files.

------
Regards,
Alexander Korotkov