BetterTrie.rb

class BetterTrie < Containers::Trie

  def initialize
    @longest_key = 0
    super
  end

  def push(key, value)
    key_length = key.to_s.length
    @longest_key = key_length if key_length > @longest_key
    super key, value
  end

  def where_key_starts_with string
    stars = @longest_key - string.to_s.length
    string = string.to_s + ("*" * stars) if stars > 0
    keys = wildcard(string)
    keys.collect{|k| get(k)}
  end

end

This is totally a hack