persistent deque (continued)

[castironpi]

Some time ago, I was asking about the feasibility of a persistent
deque, a double-ended queue.

It runs into the typical space allocation problems.  If you're storing
a pickle, you have to allocate and fragment the file you've opened,
since pickles can be variable-length strings; i.e. if the new data is
too long, blank out its entry, and grow the file.  If you're storing a
data-type, you lose Python's dynamic-type advantages, as well as its
long integers, as they can be any length.  If you change the object in
the deque, such as when using any mutable type, you have to update the
container too.

Does anyone have any experience storing pickles (I am aware of the
similarities to shelf) to a database?
Can the file system facilitate the variable-length string problem?
How feasible is a length-of-length - length - data solution to the
unbounded integer problem?
Is there any alternative to completely re-pickling a large (say 1k
pickled) object you only change slightly?
What other issues are there?
Is a hybrid-storage type possible, that stores the contents of its
Python-allocated memory block to disk, including reference count, even
if it's a lot slower?  The object could not contain any references to
objects not allocated on disk.

A first approach is for the file to look like this:

00 data 01 data 02
01 data 03 data 04
02 data 05 data 06

Append would add:

03 data 07 data 08

AppendLeft would add:

-01 data 09 data 0a

Pop would remove 03, PopLeft would remove -01.  You would need a
length-and-head index to make 'rotate' available.  Remove would run a
worst-case risk of renumbering half of the indices stored, plus a
rotate.