CODEWITHSUNDEEP
c#sqlentity-framework
RamblerToning
RamblerToning

Reputation: 976

Ordering elements in a list by a chain

I have a database of elements with a parameter that specifies the ordering, with properties like:

 ID
 Name
 Order

Let's say order is an integer - it is easy to query and order by Order. However, if I want to insert a new element in between this list, I have to go renumber everything below it - worst case scenario is when I want to push an element to the top.

So I have this idea by ordering elements by a chain. That is, I have one table with my Elements :

ID
Name

And then I have a second table with Edges :

StartNode
EndNode

And this just defines which element is connected to which other element. This way, when I want to insert an element, I just need to remove an edge and put in another one - I don't need to reorder the whole list.

But is there an efficient way to query out to get an ordered list from these two tables? Does this approach have some sort of name?

Upvotes: 1

Views: 168

Answers (1)

Gert Arnold
Gert Arnold

Reputation: 109080

Interesting question! As pointed out by starlight54, this approach is called a linked list, in particular a doubly linked list. Although I think that strictly speaking, in a linked list the references to other nodes are part of the nodes themselves. In db terms: the database record itself has foreign keys to the next and previous nodes (i.e. a doubly linked list). But that doesn't really matter for the bad news that comes now.

You're absolutely right that linked lists allow for very efficient insertion (and deletion) of nodes. But the bad news is that ordering is highly inefficient.

The point is that linked lists require sequential access: first you have to find the first node, then the next node, then the next node, ... There is no way to get the ordered list in one SQL statement containing an ORDER BY. SQL – designed for set operations – and sequential access are two different worlds.

The worst approach would be to query each node separately from the database. An improvement would be to fetch all nodes and build an ordered list in memory, but it's never going to be pleasant.

So all and all I'd stick to this Order column. Usually data are read far more often than modified, so optimizing the updating speed at the expense of easy access is not the most obvious thing to do.

Upvotes: 1

Related Questions