The key thing is "an index is a flattened tree", and for all us devs who haven't thought about trees in many years or younger folks who might not yet know, that means it's conceptually a bunch of nested maps/objects/dictionaries where the keys at each "level" are the columns in that same "level" of the index. To use a little bit of python, here's a list of the raw maps in your ascii art DB:
[
{"date": 10, "color": "red", "id": 101},
{"date": 11, "color": "blue", "id": 111},
{"date": 12, "color": "green", "id": 121},
{"date": 13, "color": "red", "id": 131},
{"date": 14, "color": "blue", "id": 141},
{"date": 14, "color": "red", "id": 142},
{"date": 15, "color": "yellow", "id": 151},
{"date": 16, "color": "blue" , "id": 161},
{"date": 17, "color": "green", "id": 171},
{"date": 18, "color": "blue", "id": 181},
{"date": 19, "color": "red", "id": 191},
{"date": 20, "color": "green", "id": 201},
]
And here's an example of how we'd represent an "index" as a set of nested maps, where that index is (date, color):
{10: {'red': [101]},
11: {'blue': [111]},
12: {'green': [121]},
13: {'red': [131]},
14: {'blue': [141],
'red': [142]},
15: {'yellow':[151]},
16: {'blue': [161]},
17: {'green': [171]},
18: {'blue': [181]},
19: {'red': [191]},
20: {'green': [201]}}
Notice that since this index is built from nested maps, if we want to use this index to find things, we HAVE to first do it by checking the keys in the "outermost" map, the 'date' column. It's a compound index but its order matters. This 'order matters' property is true in our map-based index and it's also true in our SQLite based index. It's also true that because this 'date < 17' is a range criteria, it has to check individual keys in the outermost map, which constitutes a SCAN of the index (smaller than a scan of the DB, but a scan nonetheless). To then find everything matching 'color = blue', it has to individually check all the color values in the result of the prior date SCAN in order to get down to only those with a 'color = blue'. As you can see, this index of date -> color isn't super helpful for the query 'WHERE color = blue AND date < 17' query. A query this index
would be good for is a query like 'WHERE color = red AND date = 14'. That would not require any scans; if we were writing application code such a query with this index would be like calling `index[14][red]` which as we all know is super fast.
A better index for this, which is a different index, comes from swapping the order of the columns when forming the index. Instead of (date, color), this better index would be (color, date). That index looks like this:
{'blue': {11: [111],
14: [141],
16: [161],
18: [181]},
'green': {12: [121],
17: [171],
20: [201]},
'red': {10: [101],
13: [131],
14: [142],
19: [191]},
'yellow': {15: [151]}}
Now with this new index to fulfill the exact same query of 'WHERE color = blue AND date < 17', we can do a `index[blue]` and then do a single SCAN of that intermediary to find only those `date < 17`. This still means our query does a SCAN, but it's scanning a smaller set of values (only 4 instead of at least 8 with the previous index) and we only do one scan instead of two scans.
Anyway, here's a gist of some Python if you want to play with this concept: https://gist.github.com/lelandbatey/d09557fed38c48a797bf1b15...