binary search tree

Question

can BST be used for indexing?

Comments

No

If we use BST then the height of the tree might go to O(n).

B/B++ are far better than BST

Answer 1

Yes,BST can be used for indexing,but in that case you will be using one node for a key,which is highly inefficient when it comes to storing huge database,and also SQL query won't work efficiently because in that case we have to go through various node to access particular key.

Answer 2

Binary search allows you to quickly look up a record by its key, assuming the keys are already sorted. This is especially true if the number of keys is large. 32 key reads would be sufficient to find any single unique key within a collection of two billion sorted keys.

Binary search works this way because each search attempt cuts the number of records to search in half.

That said, databases typically use some other binary tree-like data structure such as b-trees or red-black trees to perform the indexing. Using a binary tree removes the requirement that the list of keys be sorted before searching.

Reference https://stackoverflow.com/questions/9436407/how-binary-search-is-used-in-database-indexing