Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
can a node be used in different routes ? can route be modified concurrently ? –  David Oct 6 '11 at 9:31
    
A node would never be used on more than one route. If a solution enforced that a route could not be modified concurrently I believe that would be acceptable (there is no explicit requirement for route modification concurrency). –  AlexC Oct 6 '11 at 9:40
1  
"ideally to a relational database." Why? This is particularly hard. Node-graph-edge problems are not a good fit for the relational model. Why do you want to use a relational database for this? [I'm not being dismissive of your question.] Please update your question with some reason why you think a relational database is important. [You don't need to update your question if you feel that it's perfect, however.] –  S.Lott Oct 6 '11 at 14:03
    
@S.Lott I have used the term ideally in the OP to express one of the constraints is that this operation should take place within the context of functionality which is currently delivered employing a RBDMS as a persistence layer. I used the phrasing 'ideally' as that represents not the ideal platform to solve this particular problem but the ideal solution within the organisational context of the question. If the arguments away from a RDBMS for this area of functionality are sufficiently persuasive then it may be an option but there would be a lot of organisational inertia to deal with. –  AlexC Oct 6 '11 at 14:19
    
@AlexC: Do all those words simply mean "organisational inertia"? As in, "I was told to use an RDBMS"? Is that what you're saying? It's a lot of words. [I'm not being dismissive of your question.] Since you elected not to update your question, I'm forced (by the moderators) to agree that your question is (a) perfect and (b) I am utterly incapable of answering it as asked. Thank you so much for kindly providing feedback. –  S.Lott Oct 6 '11 at 14:33
show 2 more comments

3 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.