In this paper, we have shown multi-fold layered encoding mechanism that can provide fine-grained scalable storage for improving the degree of QoS adaptability. Our scheme provides both temporal scalability and fidelity scalability simultaneously, by segmenting the stored MPEG-4 data in the DCT coefficient domain as well as the temporal domain that most existing methods implement. In order to determine the reasonable set of layers, a probabilistic optimal segmenting algorithm, called J* algorithm, is defined. But, the J* algorithm is only an idealistic approach because of the huge amount of required computation time. Instead, as realistic approaches, three heuristic methods are proposed and experimentally compared with the optimal solution in terms of the average bandwidth residuum. The experiments show that the heuristics can produce relatively optimistic quality adaptation power in a simulated dynamic QoS environment, especially, the bandwidth.