Efficiently storing and modifying a reorderable data structure in a database

Question

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.

Answer 1

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!