Skip to main content
A
Anonymous
December 28, 2009
Answered

Binary Search in SQL Server 2008?

  • December 28, 2009
  • 2 replies
  • 3223 views

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

This topic has been closed for replies.
Correct answer ilssac

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.

2 replies

T
TLC-IT
Inspiring
January 5, 2010

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...

ilssac
ilssac
Inspiring
December 28, 2009

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.

A
Anonymous
December 28, 2009

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
ilssacCorrect answer
Inspiring
December 28, 2009

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.

Terms & ConditionsAccessibility statement
Using the community Terms of use Privacy Cookie preferences Do not sell or share my personal information ad choicesAdChoices