CODEWITHSUNDEEP
mysql
Bhuvan raj
Bhuvan raj

Reputation: 413

which algorithm does mysql use to search an row in the table?

If we give a query:

select name from employee where id=23102 and sir_name="raj";

I want to know using which algorithm this search will happen?

Upvotes: 7

Views: 4758

Answers (3)

Itay Moav -Malimovka
Itay Moav -Malimovka

Reputation: 53603

Assuming you have indexed the id field and it is unique.
The algorithm is a binary search (there are optimizations and improvements, but below is the general theory behind it).

Lets say you have the following ordered list of numbers:
1,45,87,111,405,568,620,945,1100,5000,5102,5238,5349,5520

Say you want to search for number 5000, There are two ways.

  1. scan the entire list, in which case you will have to check 10 numbers (count from start until you reach 5000).
  2. Binary -> here are the steps: 2a. go to middle number (620), Since 5000 is bigger then that->
    2b. You do the same on the numbers 945-5520, the median is 5102 Since 5000 is smaller then that->
    2c. go to the median of the part 945-5102, which is 1100 since it is lower then 5000 go the part between 1100-5102
    2d. Found it!

That was 4 operation against 10, so, binary search complexity will grow at the same rate as full scan when in binary search data grows exponentially

Upvotes: 10

Khez
Khez

Reputation: 10350

You can use explain and procedure analyse to find out how your query is being run by mysql.

If you want to know what kind of algorithm it internally uses to find the resulting set. I'd suggest you read up on how DBMS work.

Upvotes: 0

SQLMenace
SQLMenace

Reputation: 135021

Indexes are stored as B-trees in MySQL, Indexes on spatial data types use R-trees, MEMORY tables also support hash indexes.

Upvotes: 2

Related Questions