Name: Anonymous 2008-04-27 16:01
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
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