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.
[ Parent
| on HN ]
There are no comments on this comment yet.