Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!gatech!bbn!uwmcsd1!csd4.milw.wisc.edu!markh
From: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Newsgroups: comp.databases
Subject: Mulitple sorting
Message-ID: <5069@uwmcsd1.UUCP>
Date: 5 Mar 88 01:26:49 GMT
Sender: daemon@uwmcsd1.UUCP
Reply-To: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 16
Summary: Open problem?


     Is there a data structure or means of access that allows for all of
the following?

	(1) SIMULTANEOUS SORTING BY TWO OR MORE KEYS, 
        (2) log(N) search by ALL keys on the average,
	(3) log(N) insertion on the average,
    and (4) no redundancy. 

By the latter, I mean that there should be no duplication of the
actual memory space.  Changes made to the data when accessed
through one key should apply to the data when accessed through any
other key.  This means that one would not need to duplicate efforts
in updating.


... or is this still an open problem?