Binary Search in SQL Server 2008?

[Guest]

I recently learned about binary search in one of my classes at school, and it brought up a question in my head about accessing a database using Coldfusion.  Lets say that I create a table in MS SQL Server 2008, and I assign the table column "id" to be the primary key with auto incrementing.  If I were to perform the coldfusion statement SELECT * FROM myTable WHERE id = 'idOfRow', would a binary search be performed in this case since the id's are in sorted order?

Thanks,

Ben

[ilssac]

I doubt it.  Binary searches are cool, but they get more and more expensive in time and computing power as a data set grows.

There are much more sophisticated and powerful, but also more complicated search algorithms.  Relational database management systems (like MS SQL) have decades of very smart people working to make them better and better at storing and reteiving data.  I'm sure that index search is done with something more scalable then a simple binary search.

This is why it is almost always better to let the database do the heavy data manipluation tasks, rather then recreate the function outside of the database with an external tool such as ColdFusion.  They are designed for it by way more brain power then is probably available for your ColdFusion code.

[Guest]

Thank you for the fast reply. I am wondering about this mainly because about 95% of the queries on my website are searching by id's that are primary keys / being auto incremented.  I am hoping that doing this is beneficial in that it would allow SQL server to perform queries faster using more complex algorithms that require less than O(N) time.  Am I correct in assuming this?

Thanks,

Ben

[ilssac · Accepted solution]

Oh yes, properly indexing your tables based on how you are accessing your data is almost always the lowest hanging fruit for database optimization.  The lacking concept of your previous statement is probably that the primary key is the only index one ever needs.  But, if 95% of your access is truely based on a single primiary key field, then this is probably sufficient for your needs today.

But as one starts working with more complex data one should be sure to understand the other indexing options provided by heavy duty database management systems.

Just don't worry your head about how those indexes actually work under the hood.  Just trust that some very smart people have put in a great deal of time to make them work very well indeed.

[Guest]

Cool...Thanks!

[TLC-IT]

The typical indexing structure that is used for such purposes is called a "B-tree."

Whereas a binary-search always divides the data in half, a B-tree's approach is much more like what you might have seen in L. Frank Baum's now-famous office, where he had two filing cabinets:  "A-N" and "O-Z."  (Yes, that's where the name of the Wonderful Wizard's homeland came from.)  Once you selected from several cabinets, you now select from several drawers, then locate your starting search-position within the selected drawer and so on.  Each time, you reduce your search space by much more than one-half.

A computer-geek would say that binary search is "O(2^n)" but a B-tree is "O(x^n)" where "x" is the number of slots in each bucket.  But that's enough geekdom for one day...