News for hackers. Stuff that matters.
Re:Log Structured Merge Trees by mutex007 on Monday July 25, 2016 @08:16PM (#12162500)
I am curious how an inverted index will be implemented efficiently atop an LSM tree. Maybe batch parts of the posting list under a numeric key and when performing an intersection operation between two lists, you interate using a range scan. Could work but i wonder how fast Read operations will be. Anybody attempted yet?
Re:Log Structured Merge Trees by btrask on Monday July 25, 2016 @09:52PM (#12162891)
LSM trees are ideal for posting lists, because every time you add a new document, you need to touch potentially hundreds of different lists. LSM trees are able to batch all of these writes together. That's why Google originally developed BigTable, AFAIK.
Re:Log Structured Merge Trees by teraflop on Tuesday July 26, 2016 @03:04AM (#12163823)
In fact, Lucene (the library behind Solr and Elasticsearch) is basically a special-purpose inverted-index-as-LSM-tree database engine.
Re:Log Structured Merge Trees by abecedarius on Monday July 25, 2016 @11:55PM (#12163224)
https://github.com/kragen/500lines/tree/master/search-engine explains a simple version of this in Python.
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.