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 color isn't super helpful for the query 'WHERE color = blue AND date 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 Anyway, here's a gist of some Python if you want to play with this concept:
https://gist.github.com/lelandbatey/d09557fed38c48a797bf1b15...