I was thinking today about notebooks, and how you find information in them. When I take notes in my classes, I start at the first page, write down whatever seems important, and pick up where I left off for subsequent classes. When I want to look something up from my notes, I try to remember when we talked about it in class, and then do a sort of binary search through the notebook based on that. If I don't remember well enough, I fall back on linear search.
This is very nearly optimal for writing notes, but pretty damn bad for actually going back and reading them. (Probably, this reflects poorly on my study habits. >_>) More rigorously: Writing involves a O(log n) seek, which can be amortized over the length of a class period. Reading involves a seek which varies between O(log n) and O(n), depending on how well I remember the contents of the notebook. O(log n) is pretty acceptable performance, all things considered, but an O(n) worst case is pretty bad.
This is where the CS nerd in me immediately starts drawing comparisons to filesystems. Unfortunately, the comparisons are pretty worthless in the end, because a notebook has fundamentally different characteristics when compared to a computer's hard drive. Also, and probably more importantly, humans are fundamentally different from the computers which access hard drives - algorithms involving hashing, for example, are a no-go. Still, there's a lot of potential here for better filesystems.
First: indexing. This is basically the same algorithm used in books, for the table of contents - you dedicate a few pages at the beginning to a list of all the sections in the notebook, along with their page numbers, and then number the rest of the pages in the book. This gives you guaranteed O(size of index + log n) performance for looking stuff up, at the cost of some time every time you write in the notebook (because you have to update the index). Multi-level indexing is possible, but they don't make notebooks big enough for it to matter.
Second: file fragmentation. This is akin to what newspapers do, with continuations from the front page a few pages deeper in. If you're writing on a subject that you think you might want to come back to later, you can reserve some space at the end. When you continue writing later, on some other page, you can then go back and write the page number you continued on in that space.
Here's another thing to consider: If you use a binder instead of a notebook, you can move the pages around at will. While this is useful, it also renders your page numbers useless. This is kind of an interesting tradeoff, and it remains to see what can be done with it; I'll probably be posting on this topic again.
(Also, shameless plug: A good friend of mine (and also a frequent commenter here!) has started his own blog! Props to him for this.)