Eficientemente procurar uma hierarquia de 3 níveis

Question

Vamos dizer que eu tenho um FirstName> MiddleName> LastName hierarquia (~ 10k linhas, por causa da questão). Isto significa que você poderia ter "John> Mary-Anne> Eddy" ou "Eddy> John> Jacob" linha. O ponto é que a hierarquia faz pouco sentido e é muito estranho para o usuário (ao contrário de, digamos, uma estrutura País> State> Cidade).

Porque é tão desestruturado e confuso, eu quero dar ao usuário com uma caixa de entrada completa auto. À medida que digita, ele deve procurar possíveis correspondências de substring, e quando eles "root" sua seqüência de pesquisa em um nível, ele irá restringir os resultados para abaixo desse nível.

Agora, porque há muitas pessoas com o nome "John", não faz sentido que, se digitar "John" eles só recebem de volta os resultados como

• John> Allen> Alexander
• John> Allen> Burschawitz
• John> Allen ... repetir 100 vezes ...

Porque eles nunca verá a linha exclusiva "Jason> John> Smith".

Em vez disso, eles devem obter algo como ( "*" é apenas um indicador arbitrário para o usuário de "hey, muito mais linhas abaixo deste existe"):

• John> Allen> *
• Jason> John> Smith
• Mike> John> *
• Mary> Elena> Johnason

Se digitar "John> Al", então os resultados seriam limitados a qualquer coisa sob "John>", mas devem ser agrupados de forma semelhante ao acima.

Espero que a explicação é clara. Os requisitos são um pouco solto. Justos razoáveis, de modo que uma pessoa pode pesquisar a árvore e encontrar o que eles são depois.

Agora, eu tenho alguns SQL interessante que olha para o termo de pesquisa na linha, descobre a sua posição, faz algum substring'ing, bys grupo, ea ordem pela de obter os resultados acima, mas não é um bom desempenho suficiente .

Eu estou tentando resolver este problema em uma pilha típica LAMP (exceto com Oracle). A sua não é de hospedagem compartilhada, então eu tem controle total sobre o servidor. Os dados muda pequenas quantidades a cada poucas semanas, e os resultados da pesquisa pode ficar obsoleto para uma quantidade razoável de tempo (por exemplo, um cron que atualiza o índice de pesquisa não é fora de questão).

Answer 1

Argh. Desculpe eu não era capaz de descrever o meu problema. De qualquer forma, aqui está a solução que eu vim acima com.

Basicamente, criar uma segunda tabela da tabela de 3-coluna que contém todos os valores distintos para cada nível sucessivo da hierarquia, bem como uma coluna para indicar a profundidade da referida fileira na hierarquia.

por exemplo. De mytable(A, B, C), criar search_t(A, B, C, level)

Assim, com "One> Two> Three", você cria 3 linhas (A, B, C, nível):

• "One", null, null, 1
• "One", "Two", null, 2
• "One", "Two", "Three", 3

Ao pesquisar, você pode restringir o nível escolhendo um valor para o nível e fornecer valores para as colunas de nível superior:

WHERE A='One' and level > 1 and (B like '%t%' or C like '%t')

Pode ser um pouco simplificada e genérica, se você criar uma coluna search_str e executar a correspondência LIKE contra aquela vez.

WHERE A='One' and level > 1 and search_str like '%t%'

Em retrospecto, isso provavelmente teria sido mais evidente se os dados já estavam em um modelo de lista de adjacência.