CODEWITHSUNDEEP
databasealgorithmrelational-databasebinary-searchdatabase-indexes
user1205603
user1205603

Reputation: 111

How binary search is used in database indexing

I know how binary search works but I wanted to know practical uses for binary search... I searched through the internet and I found that the main use is data base indexing, but I couldn't understand how binary search could help in data base indexing.

Upvotes: 9

Views: 14737

Answers (3)

Rm558
Rm558

Reputation: 5002

Binary search computes next position (middle point) on each step.

DB's Binary tree precompute the middle point on each step, until reaching the single item. populate all the middle points to a tree. when do querying, DBMS looks up the tree.

Upvotes: 0

Robert Harvey
Robert Harvey

Reputation: 180808

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.

Upvotes: 7

Giscard Biamby
Giscard Biamby

Reputation: 4609

Any time you have a sorted list you can use binary search to efficiently search through the list. Database indexes are data structures of sorted data.

Upvotes: 0

Related Questions