List sorted on key1, random access on key2

I have a list of touples {key1, key2} sorted according to key1 using a B+Tree. This structure resides in secondary memmory (HDD). I want to implement an algorithm which requires lists sorted on key1 but also requires random access to the list with key2. I don't need the whole list for the algorithm, I get blocks from the disk as needed so the B+Tree works nice with all the insertions and deletions that occure.

I've been banging my head for a week and I think the only way is to use a second structure (eg a second B-Tree) with key2, but this doubles the already large开发者_运维知识库 space needed and time required to update the tree.

I don't know much about hashtables, but i don't think I can map a key to a certain value with these, right?

Do you have any idea about a structure that could provide me with random access to key2 without doubling the data?

Alternatively I could use an alternative algorithm that doesn't require random access but I want to leave that as a last solution.

Thanks in advance

I think the best way, if you're concerned about speed, is to build a hash table pointing to key2. Hashtables are generally faster on inserts and lookups than B Trees. And you won't need to double all data, just point from the hashtable to key2 in your existing structure.

Update: If you haven't worked with hashtables, read:

• http://en.wikipedia.org/wiki/Hash_table
• http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx