Implementing custom data structures

["John B" <john@...>]

Hi,

Is it feasible to implement custom data structures for Lua?  For example,
I'd like to be able to have a dictionary data structure (I'm sure that's the
wrong term technically - but I'm not sure what to call it), which would
allow for easy auto-completion.  Tables are excellent for looking up data
given a string key, but obviously they won't work with only the first part
of that key, so I need something different.  The data structure itself isn't
too hard - I know I can create a new userdata, and set up a metatable to let
me access the items, the trouble is storing those items.
Since I want to be able to reuse this in slightly different circumstances, I
don't know what type each data item will be - it could a table, a string,
anything really.  So I need some way of storing a lua object directly in my
own system.
I've considered using the registry to store the items, and just storing an
index into the registry within my own data structure, but I don't know how
efficient this will be, and I'd prefer a better way if there is one.  The
only other option I can see is to start hacking the Lua code.  Is there
another way?

Thanks in advance for any comments or suggestions,

John B