I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph database which does not support arrays; unfortunately the clear choice is not an option. Additionally it will sometimes contain hundreds of thousands of entries.

I've considered BTrees pretty heavily - they seem to provide a lot of the functionality that we need and have low computational complexity for all operations. Since we'll be selecting based on paged retrieval time and ease of implementation, a good fit will have a low computational complexity while a bad fit will be linear or worse. We only need addition to the end of the sequence, deletion (we'll have a reference to the data which will be deleted), and retrieval of a page. Pages can overlap and their size will vary. We also will want to search based on something other than order.

Are there any data structures which will be a good fit for this use case?

  • $\begingroup$ Can you specify the operations more precisely? You apparently want to do some kind of lookup operation. What is the input to that operation, and what should it return? How does deletion affect that operation? It's hard to tell what the "retrieval" operation is. Also, I don't see anything in the question mentioning that pages can overlap. And, what's the story with pages? Can we freely choose how to associate elements to pages, or is that pre-specified and not free for us to choose? Can you store an entire page's worth of elements in a single record in the database? $\endgroup$ – D.W. Jul 1 '16 at 3:05
  • $\begingroup$ Did you also considered B*-Trees? The nodes are packed more which might come in handy with your usecase of page access. $\endgroup$ – maxik Jul 1 '16 at 10:25
  • 1
    $\begingroup$ "This is being implemented in a graph database which does not support arrays" -- why?! $\endgroup$ – Raphael Jul 1 '16 at 12:36
  • $\begingroup$ @Raphael because of business constraints. $\endgroup$ – cscan Jul 1 '16 at 17:24
  • $\begingroup$ Basically, many data structures have arrays as the underlying structure. You might be able to use them in your favor. What other data structures are available to you? $\endgroup$ – orezvani Jul 4 '16 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.