Let me know if you have any questions. Happy to answer them!
I put it coded in golang there https://play.golang.org/p/hXdA0CY755
PS I like the article - I've never realized that such low level thing as L1/L2 cache are so important for query optimization!
As this is work from 2010, and, to cite from your paper:
> In this work, we will not consider finding multiple records at the same time. The algorithms given in pseudo-code will not directly support range queries. In case there is multiple matching records for the same key, the algorithms will only return one of the matching records. For most of the algorithms given here, it is however simple to extend them for range queries, or returning all of the records matching a key. We also will not consider set queries, where all records matching a set of keys are returned from one search operation. There is some potential for follow-up work in this area ...[snip]... Current commercial database systems already know when to switch from index probing to a full table scan. There might be some potential for performing better than both of those when explicitly considering this case in index structures.
The precise reason for using b-tree(-ish) data structures in databases and search engines like Lucene is precisely those two issues: to enable set and range retrievals. Have you published any follow-up of your work that extends the algorithms presented to cope with these two issues?
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.