Obligatory recommendation for the CMU Databases Systems lecture series by Andy Pavlo. https://www.youtube.com/watch?v=oeYBdghaIjc&list=PLSE8ODhjZX...
Here's the lecture on tree indexes: https://www.youtube.com/watch?v=JHZFc4hMGhk
How does database indexing work? (2008)
21–30 of 62 posts
Re: How does database indexing work? (2008)
#22I 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.)
Unless your own benchmarks prove hash indexes to have major benefits for your queries, stick with the default B-tree index: you never know what queries you'll need in the future.
That's a bit too YAGNI for me. You have a `users` table with an `tenant_id uuid not null` column. You aren't going to need uniqueness on it and you aren't going to need range operations on it it.
And..even if you did, you could re-index it.
Re: How does database indexing work? (2008)
#23Also remember to create tables using efficient structure packing and reordering[1], taking into consideration how the storage serializer operates (see [2] for PostgreSQL). An example provided by Gitlab[3] demonstrates structure packing and reordering principles in PostgreSQL. It may also be beneficial depending on types of workload to limit the number of columns in a table to optimise for locality of reference[4] once the data is deserialized into memory.
[1] http://www.catb.org/esr/structure-packing/
[2] https://www.postgresql.org/docs/14/storage-page-layout.html
[3] https://docs.gitlab.com/ee/development/ordering_table_column...
Re: How does database indexing work? (2008)
#24You know what I would like to see (for learning)?
A simplified project how indices, for example in b-tree, are stored in segment files.
Re: How does database indexing work? (2008)
#25Read here [0]
Why would I do this? [1]
[0] [https://otter.ai/u/SDndzmSLow_a2rNNzm35ohw4y9w](https://otte...
[1]
[https://www.notion.so/enoemos/https-stackoverflow-com-questi...
Re: How does database indexing work? (2008)
#26[deleted]
Re: How does database indexing work? (2008)
#27Earlier quoted context omitted.
A btree is a kind of binary tree, one which is self-balancing to keep O(log n) lookups from turning into O(n) lookups which is possible without the self-balancing. (Think about a naïve binary tree where you insert elements in sorted order—then everything will be in the right (or left if you start with the maximum value) branch and you need to traverse the whole structure to find the node you're looking for.) For sort…
> A btree is a kind of binary tree By definition a binary tree means there are two children per node. Binary is the one thing a b-tree is not .
Right, I think you could say a binary tree is a kind of B-tree, though.
Re: How does database indexing work? (2008)
#28Earlier quoted context omitted.
A btree is a kind of binary tree, one which is self-balancing to keep O(log n) lookups from turning into O(n) lookups which is possible without the self-balancing. (Think about a naïve binary tree where you insert elements in sorted order—then everything will be in the right (or left if you start with the maximum value) branch and you need to traverse the whole structure to find the node you're looking for.) For sort…
> A btree is a kind of binary tree By definition a binary tree means there are two children per node. Binary is the one thing a b-tree is not .
Uhh. A b tree is a self balancing binary (search) tree.
Re: How does database indexing work? (2008)
#29If you want to see a dumb example of how you can implement indexing on top of a SQL database without it, I wrote a tutorial on implementing basic indexes [0] as part of a series on making a SQL database from scratch. And of course, Use the Index Luke is a great reference for the real world. [0] https://notes.eatonphil.com/database-basics-indexes.html [1] https://use-the-index-luke.com/
[1] above is a fantastic resource. I highly recommend Markus Winand's book "SQL Performance Explained" if you're in need of better performing SQL queries. It's quite short and small, but it covers all the bases, and uses introductory language.
Re: How does database indexing work? (2008)
#30Earlier quoted context omitted.
> A btree is a kind of binary tree By definition a binary tree means there are two children per node. Binary is the one thing a b-tree is not .
Uhh. A b tree is a self balancing binary (search) tree.
Not binary, it can and generally has more than 2 children per node. That's the main difference.