PROBABILISTIC MODEL AND OPTIMAL REORGANIZATION OF B-TREE WITH PHYSICAL CLUSTERING()

We consider a variant of B+-tree called the B+-tree with physical clus tering (BC), which is exemplified by VSAM key-sequenced datasets. In t his file, logically contiguous data buckets are physically clustered i n a storage unit called a region in order to enhance the efficiency of sequential processing. As a consequence, records in a bucket are redi stributed over time according to two different split algorithms: bucke t split and region split A stochastic model of the disorganization of BC files is constructed using order statistics. Database administrator s of on-line transaction systems often need to reorganize BC files bef ore a region split occurs. An efficient algorithm for determining the optimal reorganization time of BC files is developed. Analytic results are validated by simulation. In passing, we discuss guidelines for lo ad-time configuration of BC files.