At 20:48 +0530 2/26/02, Battini, Chandrashekar wrote:
> Hi ,
> I am using Mysql in Linux OS. I created a table in Mysql. The
>table has 3 fields and one is Primary key among them. I have populated 40K
>entries in the table. While populating the entries in the table, For each
>500 entries that i populated in the table, i have searched for a single
>entry in the table using primary key and measured the time taken to complete
>the search. As the Number of entries grows in the table, the time taken
>to search for a entry are increasing linearly. Why is the time increases
It's impossible to say, because you don't show your table structure or
your queries. Typically, an index should speed up lookups, but it's possible
you're writing them in such a way that the index isn't being used.
> Is this the Mysql behavior? I read in Mysql manual that, by
>default Mysql creates index file(.MYI) on Primary Key using B-Tree
> My Question is , When Mysql using B-Tree for searching, Why the
>time taken to search for entries increases linearly as the entries in the
>table grows? According to B-Tree algorithm, the time has to be O(log n) ,
>which is not linear as n increases. Even though if we assume disk overhead
>as some constant (typically O(log m), where m is the order ), it is not
>linear. Why is this happening ? Can any one help me out?
> Thank You,
> Battini Chandra Sekhar.