Creating a linked list or similar queue in MySQL?

Question

I have a table of items that need to be displayed in a certain order, but that order can be changed. Items can be added at the beginning, end, or in the middle, and items can be rearranged. How can I set up the table to keep track of that order in such a way that it's easy to modify but the list can also be fetched in order with a single query?

For example, I could have a "NEXT_ID" column to do it linked list-style, but then how would I run a SELECT query to get the rows in order of the NEXT_ID chain?

Apologies in advance for the super-obvious solution I'm probably missing.

Alexandrite

See Fetching linked list in MySQL database. As noted, this is a special case of a tree. There's no way to write a MySQL query that fetches all the rows. – Revolver

Answer 1

I have this problem often, and I solved it with a simple solution : an extra column called Sort Order (or DisplayOrder, whatever floats your boat really) . This allows me the flexibility to use auto-generated, auto-incremented ID column and have a special pre-defined sort.

In my case, I need them to come out of the database with an alphabetical order except that some items like "Other" and "N/A" are always last.

ProdID ProdText SortOrder
2      "Anchovies"    1
3      "Rivet"        2
4      "N/A"          4
5      "Other"        3

SELECT ProdID, ProdText ORDER BY Sort Order

Monoclinous

Well, I'm hoping for something where I don't have to update all/several records for a single move or insertion. But based on the answers below maybe that doesn't exist in MySQL. – Alexandrite

@NChase: I've yet to find such functionality in SQL – Confiscatory

Answer 2

Create a column in the table that represents the sort order. Put an index on this column so that the MySQL engine can retrieve based on this column quickly. When you change the order, update the values in this field for all records to keep it consistent.

For example, when you insert a new record in the middle:

UPDATE table SET sort_order = sort_order + 1 WHERE sort_order >= 5;
INSERT INTO table (sort_order, column1, column2) VALUES (5, 'value1', 'value2');

Something more complicated, like moving #3 down to #6 and sliding all others up:

UPDATE table
SET sort_order = Case sort_order When 3 Then 6 Else sort_order - 1 End
WHERE sort_order BETWEEN 3 AND 6;

Unto

Answer 3

If you want to avoid the sort order, you can try a "parent" column and consider the linked list to be a special case of a tree like structure. This article may help.

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

There are other articles out there: http://ferdychristant.com/blog//archive/DOMM-7QJPM7

Keep in mind that selecting a long linked list may degrade performance though.

Presentative

Thanks for pointing it out. I reported a broken link via the mysql site. I don't hope to hear back from Oracle on that. – Presentative

Answer 4

Unless I am misunderstanding what you are looking for it would seem you could just add a DISPLAY_ORDER column that is a numeric index of how things should be returned. This can easily be changed and rearranged. Plus value can be used in order by.

Giga

I was hoping for something where I would only have to update the records that are being moved/inserted, instead of cascading the change through the entire sortOrder, but it sounds like that might not be possible. – Alexandrite

Well it isn't necessarily through all. It is only affecting the records between the range that is being changed. For example, if you move a record with the index of 3 down to 7 then you would only update records between 3 and 7. No need to change anything else. – Giga

Answer 5

easiest solution: use a column named "display_order" in which you set 1,2,3 and so on. The query would be sorted with "ORDER BY display_order".

To edit this (if youre in a website related environment) use javascript with + and - buttons for example. everytime you do + the number increments and if something with the number exists itll get decreased so they switch positions.

Community

Answer 6

You could define the "display_order" field as an Double, then use the max value in that field plus 1 as the default value. Then when you need to put a row in between two other rows, you could use the formula (row1.display_name + row2.display_name)/2.

for example, supose that the table is as follow:

id	display_order
1	1.0
2	2.0

to put an row in between 1 and 2, the display_order field should be set to (1+2)/2 = 1.5

id	display_order
1	1.0
3	1.5
2	2.0

After that you could, optionally, run the following query to bring the numbers back to "int" form:

SET @rank:=0;
UPDATE table_name
SET display_order=@rank:=@rank+1
ORDER By display_order;

id	display_order
1	1.0
3	2.0
2	3.0

Lineate