Tuplespace is all about lookups/publish/subscribe on filters on the tuples. For the vast majority of the time, filters are of the form of (<string>, <type>, ...) or (<string>, <value>, ...) . You don't need to use skip lists (or binary trees generally) for that, you can use nested hash tables on the prefix/suffix of the tuples. Then you get O(len(filters)) instead of O(log(size of tuple space)). Trust me when I say that using hashes of filters is a lot faster.
Also, see my higher-ranked post about why I stopped using tuple spaces.
