Ordered lists in django

Question

i have very simple problem. I need to create model, that represent element of ordered list. This model can be implemented like this:

class Item(models.Model):
    data = models.TextField()
    order = models.IntegerField()

or like this:

class Item(models.Model):
    data = models.TextField()
    next = models.ForeignKey('self')

What way is preferred? What drawbacks have each solution?

Answer 1

Essentially, the second solution you propose is a linked list. Linked list implemented at the database level are usually not a good idea. To retrieve a list of n elements, you will need n database access (or use complicated queries). Performance wise, retrieving a list in O(n) is awfully not efficient.

In regular code, linked list are used to get better insert performance compared to arrays (no need to move all elements around). In your database, updating all elements is not that complicated in only 2 queries :

UPDATE item.order = item.order + 1 FROM item WHERE order > 3
INSERT INTO item (order, ...) VALUES (3, ...)

I remember seeing a reuseable app that implemented all that and a nice admin interface, but I cant find it right now ...

To summarize, definitly use solution #1 and stay away from solution #2 unless you have a very very good reason not to !

Answer 2

That depends on what you want to do.

The first one seems better to make a single query in the database and get all data in the correct order

The second one seems better to insert an element between two existing elements (because in the first one you'd have to change a lot of items if the numbers are sequential)

I'd use the first one, because it seems to fit better a database table, which is how django stores model data behind the hood.