Algorithm for rdbms, select statement

hello dunno if this is the correct place to ask for this question,, im havin a thesis research and im in the algoritm now.. my thesis is an application that send messages using wherein the contacts will be query from the db..开发者_JAVA百科 so my question is what is the algorithm for searching the contacts from DB? linear search??

If the contacts field is indexed in your database, it will be using B-Tree search, hash search or a FULLTEXT search (which is combination of some more simple algorithms), depending on the type of the index and the structure of the search query.

If the contacts are not indexed or a search query structure does not allow using an index, then yes, it will be using linear search.

The index doesn't necessarily need to be primary index, it can be a index on any field. As Quassnoi said, you can specify the data structure beneath the index. Mysql assumes it to be B-tree by default. So the time to search the node will be O(logn) in case the tree is balanced, which B-tree are.

In case the contact field is not indexed, the db will linearly scan through each record and find the row until it finds one. This is worst case take O(n) time.