Tu solucion esta clara!! guarda los ids de lineage con 3 cifras (o mas) forzosamente, es decir algo asi:
100
015
015-036
015-014
015-034-068
De esa forma al ordenarlo alfanumericamente lo vas a tener como quieres ya que 015 va antes que 100.
De hecho yo uso esta funcion en mi juego para algo muy similar a lo que tu dices:
Código PHP:
// Funcion que agrega ceros a la izquierda de otra variable segun longitud dada
function agregaceros($longitud,$variable) {
return str_repeat("0",$longitud-strlen($variable)).$variable;
}