I was responding to the assertion that Lucene uses B-trees: "The precise reason for using b-tree(-ish) data structures in databases and search engines like Lucene is..."
Oh, that's why I had mentioned tree-ish structures, sort of referring to skip-lists & friends on a broad level. Sorry for the misleading expression. Rather, I'm interested if any ranged/set retrieval approach can be found that scales better than log n. (n.b. ranged, so LSH doesn't count either ;-))