In RAM, the simple implementation would be to have a balanced tree, ordered by index, where every node knows how many elements are below it, and has pointers to its children. The tree will have O(logN) depth, following a pointer is O(1), and, and all of your operations involve a small (constant-bound) number of nodes at each level.
In a typical indexed database, following a pointer (finding the row for a key) takes O(logN) time (rather than O(1) time), and it seems most of your operations would now cost O((logN)^2) time. You could hack your database's B-tree implementation, so that each B-Tree page "knows" the number of records "below" the page. At that point you would essentially be putting the RAM implementation into a file (with an optimistic assumption that Read(file, page#) is a constant-time operation in the file system). In either of the above, auto-increment works fine as long as the total number enqueued() over the lifetime of the database is not too large, but in addition to the autoincrement, you need to update the "parents" of inserted or removed records. Regards -----Original Message----- From: Matthias-Christian Ott [mailto:[email protected]] Sent: Tuesday, March 01, 2016 10:38 AM To: sqlite-users at mailinglists.sqlite.org Subject: Re: [sqlite] Random-access sequences On 01/03/16 11:59, Matthias-Christian Ott wrote: > I know that this question is not strictly related to SQLite. > > I want to persist a random-access sequence with SQLite. A > random-access sequence is a queue with random-access to its queued > elements. Suppose that a random-access sequence [x_0, ..., x_n] has the > following operations: > > enqueue([x_0, ..., x_n], x) = [x_0, ..., x_n, x] dequeue([x_0, ..., > x_n]) = [x_1, ..., x_n] lookup([x_0, ..., x_n], i) = x_i update([x_0, > ..., x_n], i, y) = > [x_0, ..., x_(i - 1), y, x_(i + 1), ... x_n] length([x_0, ..., x_n]) > = n + 1 Thinking a bit more about it, I also need the following operation: delete([x_0, ..., x_n], i) = [x_0, ..., x_(i - 1), x_(i + 1), ... x_n] So implementing the data structure with autoincrement does not work anymore. - Matthias-Christian ************************************************************************************** This e-mail and any attachments thereto may contain confidential information and/or information protected by intellectual property rights for the exclusive attention of the intended addressees named above. If you have received this transmission in error, please immediately notify the sender by return e-mail and delete this message and its attachments. Unauthorized use, copying or further full or partial distribution of this e-mail or its contents is prohibited. **************************************************************************************
