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?