# Is this index algorithm worth anything?

I have theorised a indexing algorithm (like a B-tree).

However, there's a mental block stopping me actually implementing it.

The algorithm comes in to forms:

form 1:

A look up time of O(1) to O(log2(n))

Each value in the index will have metadata associated to it that is of the size log2(n)*memory address size

form 2:

A look up time of O(1) to O(log2(n)/2)

Each value in the index will have metadata associated to it that is of the size log2(n)*2*memory address size

Unlike B-tree/other index algorithms, there's no time penalty for a add/deletion.

You can for example do a add, then do a search straight after (with no waiting in between).

You get a faster search at the expense of more metadata (memory) along with being able to insert/delete in real time.

You can also do sequential access/search sequential data values fast.

I can't find any other algorithm that has that attributes and time complexity.

If I can get it to work, I plan to sell it.

My question is; would this actually worth anything to anyone/or useful in any particular application?

Or is the amount of memory it uses too much of a deal breaker?

• I think that your question is opinion-based. There is no objective question. Even if the data structure was presented, it seems out of the scope here. – Evil Jan 8 '17 at 19:15
• What kind of items are you indexing? If we are talking about integers, then this scheme achieves $O(1)$ worst-case lookup and $O(1)$ amortized expected insertion/deletion: arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/… – akappa Jan 8 '17 at 19:40
• It's generic, it can be any type of data, integers strings etc. – eric Spam Jan 8 '17 at 19:45
• Well, if you think about it you get the same bound by hashing your input data so yeah, that wouldn't be a state-of-the-art result in algorithms and data structure (besides the substantial space occupancy per item). – akappa Jan 8 '17 at 19:49
• @akappa Make an answer? – Yuval Filmus Jan 8 '17 at 20:09

If I understand correctly, you have designed a data structure for what is known in the scientific literature as dynamic dictionary problem: keep an index I that can dynamically maintain a set S supporting queries like "is $x \in S$?" under a stream of insertions/deletions.
There are many solutions to this problem. The classical solution is to use a dynamic perfect hash function, which takes $O(1)$ worst case lookup time and $O(1)$ expected amortized update time (it's randomized) and $O(n)$ bits of space.
Moreover, your claim that "add/deletion have no penalty" is unclear to me. If your claim is that an insertion/deletion takes $O(1)$ time, then that's obviously impossible because you cannot build a data structure of size $\Omega(n \log n)$ with time complexity $O(n)$, and if you mean that they take as much time as a look-up, then your solution is no better than any self-adjusting binary tree, like AVLs or Splay trees.