Hmm, I was thinking about that while writing the post but I'm not sure that a data structure is the same as a cache, at least not in the standard meaning of the word where you save a pre-rendered version of something like a website (like what Wordpress needs), or store data closer to where you need it (like a CDN). Some databases, I think SQLite is one of them, don't even have a plain format but store all data in the b-tree.
I guess that, to me, a cache must always be redundant: you can delete its contents and lose no data, i.e., start again 'cold' and get back to the warm state algorithmically. That would make the sqlite thing (if I remember it correctly) definitely not a cache to me because the tree == the data. If I add a secondary btree in a database (also in sqlite), however, then that could be emptied with no loss of the original data, and I guess I can see the argument that it prepares the data for quicker consumption (if I'm wording that right) and so it's kind of a cache? Not sure about it though :D but I see what you mean!
A traditional cache is one form of the cache I'm referring to. What I'm arguing, is any form of "cheating" an algorithm is caching. In this case, the base case is full-table scan. If I "cheat" and pre-calculate specific queries and store that ahead of time, thats a cache.
I guess that, to me, a cache must always be redundant: you can delete its contents and lose no data, i.e., start again 'cold' and get back to the warm state algorithmically. That would make the sqlite thing (if I remember it correctly) definitely not a cache to me because the tree == the data. If I add a secondary btree in a database (also in sqlite), however, then that could be emptied with no loss of the original data, and I guess I can see the argument that it prepares the data for quicker consumption (if I'm wording that right) and so it's kind of a cache? Not sure about it though :D but I see what you mean!