News for hackers. Stuff that matters.
Re:Log Structured Merge Trees by Arkanosis on Tuesday July 26, 2016 @10:24AM (#12165798)
Done this years ago, still being used in production. In addition to the inverted lists, we have a bitmap per level, which tells whether an id is present in that level. All bitmaps are merged in memory in a structure mapping each id to the last level it is valid in. Then, lists of different levels are merged using a binary min heap. Entries that are not valid in the map are kept off the merge heap.

There are no comments on this comment yet.