Maintaining a list of nodes with challenging requirements

Question

This is a question regarding the design of a collection of ordered nodes which have some requirements that I am struggling to satisfy.

In the problem area that I am dealing with we have routes which are an ordered collection of nodes. A route will be between 1000 and 25000 nodes. A node itself is a complex object.

I need to be able to persist the nodes, ideally to a relational database (as the wider application is currently delivered using an architecture that uses a relational database for persistence). I have two separate requirements which present a difficultly in how to model the data.

1. I need to be able to insert nodes (or pointers to nodes) into the middle of the list and reorganise the list on the fly.
2. I need to be able to retrieve the list in it's correct sequential order with both an efficient index and the ability to random access.

The only way I think that I can satisfy the first requirement is to model the data as a linked list where every node points to the next node in the list, which would allow the list to be edited and reorganised on the fly.

The only way I think that I can satisfy the second requirement would be to sequentially order the list so each node has a reference to it's position in the list and order/access the list by the position.

Is there any other method that I could use that can satisfy the two requirements or am I stuck with building a hybrid that employs both methods at various times depending on operational context and that keeps the two referencing types in synch?

Answer 1

A hybrid in form of linked arrays sounds like a compromise between the two structures. You still fast index access, relatively low overhead with random insertions and really low when inserting in batches.

Wikipedia names this an unrolled linked list

Answer 2

You can satisfy both requirements by modeling routes as arrays. In a RDBMS, you might set up a table like this:

-- Table "route_steps"
id         NUMERIC   -- ID for this row
route      NUMERIC   -- FK:  Which route?
position   NUMERIC   -- Relative position of this step in the route
node       NUMERIC   -- FK:  Which node?

Inserting a step in the route would be done by INSERTing a new row and having a BEFORE trigger increment the position in all rows with a position greater than or equal to that of the new row. Deletion would be the the opposite: DELETE the row containing the step you want gone and have an AFTER trigger decrement the position of any step in the same route with a greater position than the one just deleted. Since all of this happens in a transaction, the entire operation becomes atomic.

Random access becomes pulling a row from route_steps by position:

SELECT node FROM route_steps
  WHERE route = id_of_route_of_interest
  AND position = position_of_interest

The entire route can be retrieved in sequence with:

SELECT position, node FROM route_steps
  WHERE route = id_of_route_of_interest
  ORDER BY position ASC

Proper indexing will make both of those operations very fast and will also help the UPDATEs done by the INSERT and DELETE triggers find the rows that need updating.

There are a few integrity issues that you'll need to handle, but once you get more than ankle-deep in this, you'll probably figure out what they are.

Personally, I can't see any upside in a hybrid model. You'll still have to maintain something resembling an array to speed random access using the methods described above. With that already in place, there doesn't seem to be much point in carrying out the additional work of maintaining the linked list just because it's efficient.

Answer 3

I would have a look at Boost.graph for dealing with this. It may seem like overkill at first sight but in the long run you should see more and more benefits.