AVL Tree

As always on the Arduino platform, the library would need to use as little memory and program space as possible. The SD card memory is a solid state device, so accessing a file in random order does not add a significant amount of time to the process, although the link between the SD card and the Arduino is relatively slow, and there is no caching on the Arduino side to speed things up.

What we then need is a quick algorithm for finding one item in a large list.

Choose a number between 1 and 1000. What if I bet you $1000 that I can guess what your number is by asking you no more than ten questions? Obviously my first question would be “what is your number?”. But now we restrict my questions to simply guessing a number, and your reply to be “higher”, “lower”, or “yes”. Would I still be guaranteed to win?

So, the goal is to create an index structure that will allow us to use a Binary Search so we can eliminate large chunks of data at each step of the search, and quickly arrive at the key we're looking for.

The interesting bit of coding this is to build the index in an efficient way, so that it will remain quick to search, even though the records to be read or written are presented to the library in any order. We can assume each record will usually be read more times than it is written, so it's more efficient to spend a little time storing things in the “right place” and tidying up as we go, so they can be quickly retrieved later.

Wikipedia has a nice description of AVL Trees, and enough pseudo code to get me started along the right path.