List:Internals« Previous MessageNext Message »
From:Michael Widenius Date:May 2 2001 1:40pm
Subject:Multiple column indexes
View as plain text  

>>>>> "Russell" == Russell King <webmaster@stripped> writes:

Russell> Hi,
Russell> I'm currently in the process of using MySQL to map a 2-dimensional
Russell> section of a galaxy (for a game), and consequently often retrieve all
Russell> the entries withing a certain x and y range.

Russell> However, doing a range search on more than 1 column appears to take much
Russell> longer than expected. Looking into it the system concatenates the two
Russell> column indexes, making range searching only possible on one of the
Russell> columns. I presume the system searches using a binary-tree or hashing
Russell> algorithm at present.

Yes, we us a binary-tree for this.

Russell> Are there any plans to use a quad-tree or oct-tree for 2 and 3 column
Russell> indexes in the future. I've written a quad-tree implementation for my
Russell> 1.4 million point database, and it returns all points within a given
Russell> range in around 0.006s  as compared to 3.5s.

Russell> Regards,
Russell> Russell King

We plan to in the future use rec-trees for things like this;  The only
problem is to get Sergei time to do the actual coding on the lower
level and then extend the optimizer to recognize these types of

Is this something that you could be interested in helping us do?

Multiple column indexesRussell King30 Apr
  • Multiple column indexesMichael Widenius2 May