Quick recap on Binary Search Trees

Chronicles of DB Indexes - Part 2

Continuing the series on Indexes with the egg of all indexes (yes, egg is argued to be older) - the Binary Search Tree (BST) itself!

I have to warn you, though. I'm not going to teach you the basics that are available everywhere on the internet. These articles serve as a REMINDER, but if you have no clue what BST is - Google it! It's really damn simple!

In order to fully grasp WHY B-Trees and how it all fits together, I'm doing this quick recap on BSTs. Beacause, you know, B-Trees are sometimes called "variation" of a Binary Tree.

Important thing to note about BSTs is that they are fast in-memory structure. And they also happen to grow in depth (i.e. they get taller), because, the more data you add, the deeper your tree becomes. This is in contrast to B-Trees which become bulkier (i.e. they spread in width).

Important thing that distinguishes Binary Search Trees (BST) and Binary Trees is that in BST, all children are (and grand children) are HIGHER than parent, whereas all children to the LEFT are always smaller. This is true all the way from top to bottom!

Binary Trees in contrast don't have any constraints except that they must have up two two childs. But that's about it. Crap is that literature usually refers to BSTs but calls them Binary Trees. Be aware of it!

And that's all there is, really!

Next article will cover B-Trees and why they were made for HDD storage.

Until then - feedback is welcome!