Re: Big O

In article <u54i63m3gt0628_at_corp.supernews.com>, Nashirak Bosk wrote:
> I am writing something on the advantages of Databases over flatfile
> systems in most Commercial Situations. Does anyone know the search times
> (in the order of Big O)?? I am thinking its pretty close to O(1)
> (Through hashing) but does anyone know about the average big O for most
> Databases?

O(1) as you pointed out correctly can be achieved with nearly ideal hashing. Most databases use some sort of B-Trees though to implement the index and B-Trees are balanced multi-way trees, i. e. you have access times of O(log n) where n is the number of items stored in the tree.

Some databases offer additional datatypes or let the user define some for -- let's say -- spatial data. The index for such spatial information is usually implemented with its own datastructure e. g. R-Trees or UB-Trees and the like. So search times can vary in these cases.

For general purpose though, you'd be well adviced to examine B-Trees.

Andi.

-- 
Andreas Bauer, baueran at in.tum.de, http://home.in.tum.de/baueran/
"Facts are meaningless. You could use facts to prove anything that's
even remotely true!" -- Homer Simpson