How can I structure my database tables in such a way that their orders can be rearranged at any time?

Question

I'm working on a personal project that basically saves the output from a rich-text editor into a database so it can be accessed again later on a different device. The user can add "pages" to the notes for different chapters or subjects.

The problem I ran into is that I'm unable to rearrange the order of the notes, or insert a new page somewhere. My current solution is to have 2 IDs - one is the primary index (ID), and the other one is a relative ID (RID). To rearrange the rows, I just change the RID of that row, then sort the rows by RID when displaying them.

ID | RID | page_title | page_content
01 | 01  | Hello      | Hello world
02 | 02  | Goodbye    | See ya

This works when I have very few pages, but if I had 100 pages and I'd like to rearrange or insert a new row in the middle, I'd have to change the RID for every row below where the change was made.

What's the proper way to structure my table such that it's easy to rearrange or insert into later? I'm familiar with MySQL using PhpMyAdmin, and SQLite using SQLAlchemy.

Sorry if this has been asked before, it's hard to phrase the question into a google search, I kept getting irrelevant results. Thanks in advance!

score 1 · Accepted Answer · answered Mar 15 '20 at 05:36

1

There are many ways to do this. One simple way would be to treat the pages as a linked list. Instead of an order column, use a prior column that points to (FK) the page that preceded these page.

E.g. starting with pages in a-b-c-d order:

id, page name, prior
1, a, null
2, b, 1
3, c, 2
4, d, 3
5, e, 4

To move page “b” to after page “d”, you would:

(1) change c’s prior to 1

(2) change b’s prior to 4

(3) change e’s prior to 2

Do all that inside a transaction and you’re golden. The new list looks like this:

id, page name, prior
1, a, null
2, b, 4
3, c, 1
4, d, 3
5, e, 2

The same number of operations (3 for a singly-linked list) will be needed no matter how many total pages you have.

Be sure to test your implementation for moving the first page (prior=null) since that’s a special case.

answered Mar 15 '20 at 05:36

Chris Johnson

20,650
6
81
80

Thank you, this is great for swapping, but what about inserting? Let’s say I have a new page f that I want just after page c in the original order. I’d still have to add 1 to all the items below the new position for page f. – Panpaper Mar 15 '20 at 07:15
No, because the `prior` column says which node by ID comes before this node. In my second data set above, the order is a-c-d-b-e. If you wanted to add a new item `x` after `b`, you would create a new entry `x` with `id` = 6 and `prior` = 2 (meaning, after `b`) and change the node that previously pointed to `b` (`e` since its prior was `2`) to use `prior` = 6. This is basically just a singly-linked list in a database. Look up the standard implementation for a linked list to understand how to insert, move, delete, sort etc. – Chris Johnson Mar 20 '20 at 14:12
The `prior` column is not a “sort-by” column, it’s a “which node, by ID, comes before this node” column. – Chris Johnson Mar 20 '20 at 14:14
I took your advice but used a doubly-linked list instead. Works great for inserts, deletes, and swaps! However, I couldn't figure out how to display all the items in the list. I posted [a question](https://stackoverflow.com/questions/61006748/how-to-display-linked-data-from-database-in-flask) but couldn't get any help. Would you mind taking a look? Thanks again! – Panpaper Apr 05 '20 at 02:28

Panpaper · Answer 2 · 2020-03-15T07:58:04.507

I just thought of another solution, but I don’t know what kind of disadvantages this might come with.

Save the order as a list of IDs (I.e. 1, 2, 3, 4, 5) to a separate table along with a list ID.

(Pages Table)
ID, page, listID
1, a, 1
2, b, 1
3, c, 1
4, d, 1
5, e, 1

(Lists Table)
ListID, list_sequence
1, (1,2,3,4,5)

Every time the order changes, save the new order to the Lists Table. When retrieving the data to display, first retrieve the list_sequence from the Lists Table, then do something like

for id in list_sequence:
    Pages.query.get(id)
    // display the row

This way, the rows will be retrieved sequentially according to the specified order. Each rearrangement would only write to the database one time.

Please let me know if there’s a good reason not to use this method!

Edit: the list_sequence column would be saved as a string.

Edit 2: This would add another operation for every insertion. The new row will have to be inserted, and then the list_sequence would have to be updated too. Would this be a very significant difference in terms of speed?

How can I structure my database tables in such a way that their orders can be rearranged at any time?

2 Answers2