(Double) Linked Lists

I've been trying to write a little forum application that scales to million of threads in a category and million posts in a thread. The idea is that viewing a category or thread on any page will only take n+const key lookups in a database (like berkeleydb) where n is the number of items (threads or posts) on the page.

Implementing threads and posts as double linked lists makes it really easy to view the oldest and newest items (and adding new items) but obviously pagination doesn't work at all and also deletion is going to be a bitch because you have to "find" the item first.

I've been thinking about adding "shortcuts" to every 10th, 100th, 1000th, etc item to the next 10th, 100th, 1000th, etc item, but then deleting becomes very very expensive because you possibly have to update thousands of shortcuts. Is there a solution that doesn't suffer from having one really bad operation (or requires in-memory indices)? Or maybe a n+log(items)+const solution...

This is just a thought experiment about data structures but it has been driving me kinda nuts lately :p

>>40
Hash tables have O(n) worst case performance too, but you can't rearrange them to fix it.

>>41
O(n) until they're saturated.

>>40
binary trees have O(n) worst case performance
Did you mean O(log n)?

>>42
Did you mean O(log n)?
Worst case: A degenerate tree, which is essentially a linked list, which is O(n)

>>43
Such a thing wouldn't happen if you rebalance the tree when modifying it.

>>45

You can't rebalance a B-tree. But you could rebalance a hash table.

>>45
You can rebalance a B-tree, but you cannot tune a fish.

>>45
Your post has severe internal inconsistencies. Please fsck before mounting.

FSCK MY ANUS

>>48
I do not endorse this.

>>48
But you can't tune a fish sandwich.

>>50
But you can sandwich a fish tune.

ITT, kids who don't understand the practicalities of implementing this. And who don't understand what a modified preorder tree traversal is, or why its the best solution.

>>52
fag