I am not sure if I get this right. I'm designing a database model for use in an application, and I'm stuck at a doubly linked list (model first; there is no code yet).

There's an order. An order has an owner who gives it to someone, an acceptor. The acceptor can decide to divide the order into suborders. He will then become the owner of these suborders and give them to other acceptors. An order can have infinite Suborders, which can also have infinite Suborders and so on. Typical hierarchy. But the (sub-) orders have to be in order (no pun intended), and it would be nice if they could refer to the predecessor and the successor. Predecessor to the first suborder would either be null oder the parent order, successor to the last order either null or the parent order.

What is the best practice in such a case? I feel that the following is a bit... too much clutter (suborders would be a collection).

2 Answers 2


I'm not sure I understand your question right, but:

If I understand right, this is a tree that has children ordered. Also the creation of children is monotone, that is no children are deleted. In these cases, in relational databases I used to have:

  • Id

  • parent's Id

  • child order (first child is 1, second 2, etc.)

  • child count (count of my children, only needed if you want "last child")

  • acceptor, ...

Key's are ( Id ) & ( parent's ID ; child order ).

In this case:

  1. Previous sibling is ( parent's Id ; child order-1 )
  2. Next sibling is ( parent's Id ; child order+1 )
  3. First child is ( Id ; 1 )
  4. Last child is ( Id ; child count )
  5. Parent id ( parent's Id )

I hope I helped.

  • You understood it right, thank you! This is exactly what I was looking for. @branko-dimitrijevic answered it the same way, so I think this really is the best practice ;)
    – Trevor
    May 27, 2013 at 10:25

You have two issues here:

  1. Representing hierarchical data.
  2. Providing order at each level of hierarchy.

Probably the simplest way to do it is to use the "adjacency list" for representing hierarchy and order field for representing order:

enter image description here


  • The PARENT_ID is a foreign key that references ITEM_ID, denoted by FK1.
  • There is an alternate key on {PARENT_ID, ORDER_IN_PARENT}, denoted by U1.
  • Both PARENT_ID and ORDER_IN_PARENT are NULL-able.
  • There is only one root where these fields are actually NULL.

So, to traverse the whole "list" in-order, start from the root, select its children in order, select children's children, etc. recursively...

A sibling can be reached simply by getting the item that belongs to the same parent, having the smallest ORDER_IN_PARENT larger than the starting item. If there is no such node, go to one level up and repeat...

Child levels can be added/split/deleted naturally.

Alternatively, you could use "nested sets" model, which in addition to its basic function of representing a hierarchy also naturally orders the items. Bill Karwin has a nice presentation about various ways for representing hierarchies.

1 SELECT * FROM ITEM WHERE PARENT_ID = :parent_id ORDER BY ORDER_IN_PARENT. On a DBMS that supports recursive queries, it might be possible to do that in a single query.

  • Thank you! This is basically the same solution as @Szidor wrote, and it looks really neat. But, in my case, there can be more than one "root", since there is not only one top order. So I guess PARENT_ID will point to itself when an order has no parent order.
    – Trevor
    May 27, 2013 at 10:25
  • And what is the order or top orders? I think what you refer to as "top order" is the first level of children in my model. May 27, 2013 at 10:48
  • There is no sort order in the first level, since these orders are independent orders from different owners. So there is no need to sort them.
    – Trevor
    May 27, 2013 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.