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.