0

Suppose I am given a range of integer (for example, from 1 to 8000000). These integers are represented as an ID for an item. The program can detach that integer from an item such that next item can reuse it.

Store an individual integer in a database row is not feasible as it can goes up to couple billions integer there.

I am thinking to use interval tree to find the 'gap' but then I need to store it in a mysql database.

Is there any other choice?

Note: It is not a college homework. :)

Kintarō
  • 2,947
  • 10
  • 48
  • 75
  • Imagine that some process went through your table and deleted every second ID. Now your interval tree takes up more storage than if you were to keep every available ID in a table. What about using bitflags to represent availability? That would require 1000000 bytes. A bit ridiculous, but it kinda depends on what kind of holes you expect in your data. – paddy Jul 31 '15 at 00:53
  • I don't want to say this is the answer but, depending on the problem, it might be easier, more memory efficient, and faster to keep track of what integers have been taken and then infer which ones are available. – aug Jul 31 '15 at 00:54
  • possible duplicate of [How to find a "gap" in running counter with SQL?](http://stackoverflow.com/questions/1312101/how-to-find-a-gap-in-running-counter-with-sql) – schtever Jul 31 '15 at 01:03

1 Answers1

1

Store an individual integer in a database row is not feasible as it can goes up to couple billions integer there.

I'm a bit confused. 8,000,000 is not a "couple billion integer". It is 8 million. This is very feasible for storing in a table.

My vote is to create a table. This could be 8 million integers with a primary key and an indicator of whether they are chosen. Or, it could just be a single table of integers that have (or have not) been used.

Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786
  • It is 8 billions but you are right. After thinking about it, I think I don't need to go up to 8 billions so it will just use a table to store it. – Kintarō Jul 31 '15 at 03:41