Improvements on tree index class
You can build it faster and use it faster if you use a flat hash instead of cascading hashes.

Here's a simple implementation using a "flat" hash:

class QuickerIndex

  def initialize(array)
    @index = {}
    array.each_with_index do |item, i|
      (@index[item.to_s] ||= []) &lt;&lt; i
    end
  end

  def index(item)
    @index[item.to_s]
  end

end


and a benchmark to compare the two:

require 'benchmark'
floats = 10_000.times.map{rand}
Benchmark.benchmark('', 20) do |x|
  index = nil
  x.report('cascading create:') {index = QuickIndex.new(floats)}
  x.report('cascading access:') do
    floats.each do |float|
      index.index(float)
    end
  end
  x.report('flat create:') {index = QuickerIndex.new(floats)}
  x.report('flat access:')  do
    floats.each do |float|
      index.index(float)
    end
  end
end


CPU

No duplicate items

Without duplicate items, the CPU time needed to create and access various sizes of indices were:

                    ------CREATE--------     -----ACCESS------
NUMBER OF FLOATS    CASCADING       FLAT     CASCADING    FLAT
    10,000             0.27         0.05          0.20    0.03
   100,000             3.98         0.45          2.42    0.43
 1,000,000           140.75        14.13         69.72    4.84


With no duplicate items, flat hash scales a little better than cascading hash in create, but much better in access.  Flat hash is faster for create and access.

Duplicate items

Now, what about repeated items?  You indicate that there is some likelihood that two items will share the same key (that is, have the same #to_s).  Let's assume that each number is duplicated 10 times.  That is, in a list of 10,000 floats, there are really 1,000 unique floats; in a list of 100,000 floats, there are 10,000 unique floats:

                    ------CREATE--------     -----ACCESS------
NUMBER OF FLOATS    CASCADING       FLAT     CASCADING    FLAT
    10,000              0.23        0.02       0.20       0.02
   100,000              2.20        0.26       2.12       0.21
 1,000,000             27.70        3.56      26.29       2.62
10,000,000            364.14       25.16     341.66      23.44


Both flat and cascading hash perform better with duplicate items than without.  Flat hash still scales better, and is always faster.

Memory

Unless compiled with the right switch, Ruby lacks an effective way to tell how much memory is in use by its objects.  As a proxy, we can use "ps", which reports the total process size in kilobytes.  It's an imperfect proxy, but it's the best we have.

Here are the numbers for various numbers of floats.  The number of unique floats was always kept at 1/10th the total number of floats.  The memory size reported is the amount that memory usage went up after creating the instance of the index class:

NUMBER OF FLOATS    CASCADING        FLAT
    10,000             2,048k         52k
   100,000            32,952k      1,664k
 1,000,000           232,868k     28,596k 
10,000,000         2,232,568K    229,512k