DEV Community


Discussion on: How Do We Get a Balanced Binary Tree?

patarapolw profile image
Pacharapol Withayasakpunt

Why does it have to be binary?

I am currently interested in how B-tree or B+tree works, or even how filesystem works...

To my knowledge mainstream relational databases (MySQL, PostgreSQL, SQLite) all use a form of B-tree, because hashtable is not good for comparison. Abstractly you can view B-tree as a sorted set while a hashtable an unordered set. For string operations I suspect they are just implemented as regular expressions, which if you limit them to no look back can be implemented efficiently as finite state machines.