How does database indexing work? (2008)
stackoverflow.com
How does database indexing work? (2008)
1–10 of 62 posts
Re: How does database indexing work? (2008)
#2...the same way as non-database indexing? e.g. a lookup table for values in a different order than they're stored
Re: How does database indexing work? (2008)
#3...the same way as non-database indexing? e.g. a lookup table for values in a different order than they're stored
It is, but with all respect, it’s not a useful answer (or even accurate; see below). If one takes, for example and contrast, the top-voted answer, well, I could probably implement a database index scheme of some sort based on that explanation. Might not be a good one, but it would work. Parent comment’s answer? I wouldn’t know where to start.
Additionally, parent’s answer doesn’t actually answer the question, by saying what an index is, but the question was “how does it work?” The top SO answer does a great job with this one, I think. Another one a few answer down also goes into some of the downsides (it slows down writes, for one). The whole page is worth a skim if you’re not a DBA but have to fiddle with DBs on occasion.
Re: How does database indexing work? (2008)
#4Does anyone know what an index card was?
Re: How does database indexing work? (2008)
#5...the same way as non-database indexing? e.g. a lookup table for values in a different order than they're stored
This feels a bit reductionary. Database indexes definitely have more to consider than just simple lookup tables. I’d say that mental model breaks down in practice.
Re: How does database indexing work? (2008)
#6Does anyone know what an index card was?
In school and public libraries it was a physical piece of thick paper, similar to a Rolodex card, which had multiple copies, always one per author and one per title, but sometimes backups by subject manager. And when I was a kid, there were often multiple, redundant copies that one could take to the librarian to check out the physical book if it were particularly important.
Yep, that old :(
Re: How does database indexing work? (2008)
#7...the same way as non-database indexing? e.g. a lookup table for values in a different order than they're stored
There's kind of three things you want to show people to get them to understand indexes. Let's say you sell an internet police service and have a table of URLs you are crawling for a table of clients, each client gets some client_id, each URL references the client_id of the client who wants it policed. Here are the things you want to say:
1. Binary search. It's be really handy to have the URLs stored in a different order, maybe grouped by client_id first and then all the URLs for the same client are alphabetical. The index conceptually just contains the same rows in a different order.
2. The read vs write trade-off. Your data fits in memory if there's less than 10 TB of it (possibly up to 100 TB) so the big thing is latency, what an index does is, it requires you to write the same information twice in order to read it exponentially faster, so depending on how often do you write versus how often you read, indexes make less or more sense.
3. High fan-out trees. Once you have explained that the index is just an the same data in a different order, you have inserted a sort of ticking time bomb of misunderstanding. The problem is, a beginner programmer’s notion of a freely indexable list, such that binary search works on it, is an array. How do we insert into an array? With all the work of array copies! So you get people who think that random ID columns should never be indexed, because every write into the middle of the array has to shove half the data one cell to the right—unacceptable! So it really helps to say, “now we can store this as a binary tree, make one comparison per level of the tree.” Pause for understanding that the “list,” can be stored with such a tree. “but, modern computers have a nice property that right after accessing some memory the memory near that location is loaded into a cache... this makes arrays real fast. Suppose we don't just have the binary tree thing of 2 child nodes each representing 50% of our data, but an array with 100 pointers each representing 1% of the data, you get something like a 6x memory speedup from the cache, because your tree is one sixth the depth of the binary tree. And that's basically what a B-tree is, you use a higher fan-out of your sort tree to exploit the cache.”
Re: How does database indexing work? (2008)
#8I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
Re: How does database indexing work? (2008)
#9Does anyone know what an index card was?
In school and public libraries it was a physical piece of thick paper, similar to a Rolodex card, which had multiple copies, always one per author and one per title, but sometimes backups by subject manager. And when I was a kid, there were often multiple, redundant copies that one could take to the librarian to check out the physical book if it were particularly important. Yep, that old :(
Wait, you had card catalogs where you took the cards out of the drawer? I grew up with card catalogs where there was a metal rod at the bottom of each drawer that ran through holes in the bottom of the cards. There were cards for author, title and subject with multiple subject card possible for each book. The CIP blocks on the copyright pages of books list all the possible subject headings.
And I've been thinking that I don't use the subject indexes on the online catalog anywhere near enough. They can surface things that the standard keyword search might miss or bury among irrelevant results.
Re: How does database indexing work? (2008)
#10I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
theoretically a hash lookup is O(1) so should perform better if the key is unique, but you give up a lot of other features (like partial matches, searching, and range queries).
Binary trees are the ideal in a world of a pure von Neumann model. In practice data structures perform better when data is grouped together and this is what the b-tree gets you. It's both more disk and cache efficient in real world workflows