  We present quantum algorithms to search for marked vertices in structured
databases with low connectivity. Adopting a multi-stage search process, we
achieve a success probability close to $100\%$ on Cayley trees with large
branching factors. We find that the number of stages required is given by the
height of the Cayley tree. At each stage, the jumping rate should be chosen as
different values. The dominant term of the runtime in the search process is
proportional to $N^{(2r-1)/2r}$ for the Cayley tree of height $r$ with $N$
vertices. We further find that one can control the number of stages by
adjusting the weight of the edges in the graphs. The multi-stage search process
can be merged into a single stage, and then an optimal runtime proportional to
$\sqrt{N}$ is achieved, yielding a substantial speedup. The search process is
quite robust under various kinds of small perturbations.
