At 3AM. That's how ya know I'm coding. Did ya catch the error in my last post? The midpoint may only change half a record for an addition or deletion, but that could potentially mean updating every record in the database. Can't have that. For the link one jump forward or back that's just three writes. But for the midpoint links that's not gonna work. So I've devised an evil plan. I will adjust the current link to those of the second link forward. Adjusting my links 3/4 forward or back and only update 3 or 4 links either side. Over time all the links will adjust to the growth in the database even though some links will fall short of half and others will overshoot. No sleep and I'm still this brilliant! Who'da thunk it? Well, if it works?
Speaking of pizza. Eating it cold for breakfast is how you find out if it really was good. Not so much in this town. I like the owners, but nobody in town really knows how to make a great pizza. I had friends in Seattle that used to rave about some of their pizza places, but putting exotic stuff on a pizza is not what makes a good pie. A plain cheese pizza almost anywhere in Brooklyn, NY beats almost anything any place else. In NYC they did sometimes try to get a little fancier. I once had a ricotta and broccoli pie that was pretty good, but the only thing they did fancy in Brooklyn was stretch the dough.
How many links forward or back should I update? I'm thinking log10(db size, that's record count, not bytes) should be about right?
What about records marked deleted? I can still use those links that will still exist. If a new record had been updated there I can follow it's link (whichever side I'm following to the first record with a usable link.) For a record marked deleted a one direction link can be put in the data field so we don't overwrite the still usable old links.
One last point. 32bit links will be large enough and 16 bit counts will do the trick so that's about 18 bytes of overhead per record. However, strings will store a 4 bytes pointer to records that have no links at all. So 40 bytes per record should be enough for 200 bytes of string data (two bytes reserved per record.) Wait, actually string records could be a linked lists (unrelated to those other links so I really have almost unlimited space up to 160 billion bytes of data! If I count by record size rather than actual byte position.)