pythondatabasebinary-search-tree

What is the importance of implementing binary search trees (BST) for our database?


Binary search trees (BST) are helpful to perform CRUD operations efficiently. Do we need to implement a BST in a programming language when storing data in a database?

For example, consider Django + Postgresql. The models in the Django framework automatically convert into database tables using an ORM. I never had to implement these trees. Are BSTs built into databases or does it make sense to implement them?


Solution

  • Proper database engines (including PostgreSQL) implement efficient CRUD mechanisms. BST is just one possible datastructure to use with an index, but in practice databases use B-trees or B+-trees for this purpose. You don't need to implement this yourself.

    Just like a balanced BST, B(+)-trees are balanced data structures that offer CRUD operations with logarithmic time complexity when given a key for which an index exists.

    See Wikipedia on B-tree:

    a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems.

    When you design your data model, you should just take care that you define the necessary table indexes, so you take advantage of this.