The need always exists for indexing mechanisms that can precisely retrieve imagery from a database, as well as maintain certain efficiencies for large-scale image database search. To achieve this, we developed a hybrid search tree called SKD-Metric tree. This novel approach merges the classification power of the statistical k-dimensional tree and the efficiency of computation of the Metric-tree for nearest neighbor (NN) search. Another feature of SKD-Metric tree is its flexibility to formulate a new metric function while the retrieval system utilizes user's feedback to improve accuracy. In addition, unlike traditional relevance feedback approaches that, in most cases, sequentially search the entire database to obtain new retrieval results, SKD-Metric tree features a fast retrieval refinement procedure that needs to update only a small portion of the database. An extensive study, based on experiments performed for evaluating retrieval precision and computational efficiencies, is presented. We have applied our approach to a large-scale medical image database. The experimental results show that SKD-Metric tree can achieve a high accuracy rate with dynamic relevance feedback that requires much less computation than existing techniques.