# Efficiently storing and modifying a reorderable data structure in a database

I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each item, but with the reordering requirements, that would mean renumbering everything with a higher order (down the list) than the place where you removed or where you inserted the moved item. So I started looking at data structures that were friendly to reordering, or to both deletion and insertion. I'm looking at binary trees, probably red-black trees or something like that. I feel like I could with great effort probably implement the algorithms for manipulating those.

So here's my actual question. All the tree tutorials assume you're creating these trees in memory, usually through instantiating a simple Node class or whatever. But I'm going to be using a database to persist these structures, right? So one issue is how do I represent this data, which is kind of a broad question, sure. I would like to not have to read the whole tree from the database to update the order of one item in the list. But then again if I have to modify a lot of nodes that are stored as separate documents, that's going to be expensive too, even if I have an index on the relevant fields, right? Like, every time I need to manipulate a node I need to actually find it in the database first, I think.

Also, I obviously need the content and order of each node on the front end in order to display the list, but do I need the client to know the whole tree structure in order to be able to send updates to the server, or can I just send the item id and its new position in the list or something?

I'm sorry if this veers too practical but I thought someone might want to take a crack at it.

• practical answer that isn't helpful to the conceptual question here: many modern relational databases allow for array data types that would probably work for you. Better Answer: Good question! I don't know the best way to do this! You don't need a tree to do this efficiently I think. You can just use a linked list with the primary key of the node table being used like an address. Removal requires a transaction with one update and one deletion. Insertion requires a transaction with one read, one insert, and one update. Each node would have a primary key, a list id, a next key, and content – Jake Jun 30 '20 at 4:55
• As a general comment, a number system that will solve the problem (given arbitrary-precision integers) is to represent a position as a fraction p/q, represented as a pair of integers. The initial order is 1/1, 2/1, 3/1, etc. Then to move an entry between a/b and c/d, use (a+b)/(c+d). If you were implementing sorting yourself, you could compare a/b and c/d using ad < bc, but how you would do this in a SQL-like language eludes me. – Pseudonym Jun 30 '20 at 5:06
• What operations do you want the data structure to support? How large will lists be? I am suspicious that the time to access the database will be so huge that reading the entire list, reordering the desired elements, and writing it back might perform almost as well as more sophisticated solutions. – D.W. Jun 30 '20 at 8:34
• Reordering cannot be done in strictly less than $O(log(n))$ comparisons between items, as it would violate the known rule that comparison-based sorts take $\Omega(nlog(n))$ time. So, doing any naive implementation using priorities represented as numbers would probably not be efficient enough – nir shahar Jun 30 '20 at 9:00
• @Pseudonym that's roughly what Dietz-Sleator algorithm does, but with eventual re-numberings instead of arbitrary precision. (Well, simplified version by Bender et al. does that.) – Dmitri Urbanowicz Jun 30 '20 at 10:09

There are two questions here:

1. How do you implement a pointer data structure such as a red-black tree in a database?
2. Should you implement a pointer data structure in your database to solve this problem in practice?

The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For example, to implement red-black trees in a typical relational database, you would have a table with one row for each node, with the following columns:

• an autoincrement non-nullable integer primary key column, storing the node ID
• three nullable integer columns, storing the left, right, and parent node IDs
• a non-nullable bit column, storing the red-black flag
• columns for whatever actual data is associated with each node

And then you would have a table with one row for each tree, with an integer column pointing to the root node for that tree.

As for (2): if your lists are less than a few thousand elements, it's definitely likely—as @D.W. points out—that the best way to store the ordering in a database is not to do the above. Skip the pointer columns and just give your table of lists a blob column that stores that list's item IDs in order as a series of 2-byte or 4-byte ints. When your app wants to show the list, it reads the entire blob for that list; when it wants to reorder a list, it overwrites that list's blob with an entire new blob. [*]

If your lists are large enough, you might want to start profiling different options' performance. But you mention a drag-and-drop UI, and such UIs are rarely amenable to reordering lists longer than even a few dozen elements.

[*] Implementation note: If you go with this option, make sure you have another column on the items tracking which list each item belongs to, rather than just using a single autoincrement ID column. Otherwise, repeatedly creating and deleting lists could overflow your IDs even if each individual list only has a few items in it!

• Hey thanks! I was wondering if maybe I was overcomplicating things for my humble list app, I think I'll try what you end up suggesting. – etd Jun 30 '20 at 15:16
• @etd See the implementation note I added too. Maybe obvious, but I thought it was worth saying explicitly. – Aaron Rotenberg Jun 30 '20 at 17:27