I wonder whether you can enhance a skip list to store secondary indices compactly. Hm. I should try the obvious first, probably.