Last I checked, Lucene doesn't use B-trees. It uses a variation on skip lists to implement efficient inverted indices. As I understand it, its performance come

Last I checked, Lucene doesn't use B-trees. It uses a variation on skip lists to implement efficient inverted indices. As I understand it, its performance comes from a column-store-like approach where large document lists can be efficiently intersected. Lucene also uses a LSM-style approach when writing index files; instead of updating a single large index in place, it incrementally appends to new partial index files, and to execute a query it queries every partial index and merges the results. (These partial index files are then incrementally merged in the background to reduce the number of files that need to be aggregated at query time.) Lucene is slower than an RDBMS on narrowly targeted queries where an RDBMS can use a B-tree, but is more efficient when a query matches many documents because its index data structures are more efficient than a classical "sequential scan" across row pages.