Online Reorganization of B+tree in a Scalable and Highly Available Database Cluster

On-line reorganization in a shared nothing database cluster is crucial to the performance of the database system in a dynamic environment like WWW where the number of users grows rapidly and changing access patterns may exhibit high skew. In the existing method of on-line reorganization have a drawback that needs excessive data migrations in case more than two nodes within a cluster have overload at the same time. In this paper, we propose an advanced B tree based on-line reorganization method that solves data skew on multi-nodes. Our method facilitates fast and efficient data migration by including spare nodes that are added to cluster through on-line scaling. Also we apply CSB tree (Cache Sensitive B tree) to our method instead of B tree for fast select and update queries. We conducted performance study and implemented the method on Ultra Fault-Tolerant Database Cluster developed for high scalability and availability. Empirical results demonstrate that our proposed method is indeed effective and fast than the existing method. method.