The Study And Optimization Of RTDB Index Structure Based On The Red-Black Tree Balance Mechanism

Now, the real-time database (RTDB) has been more and more widely used, it must maintain object consistency constraints and to ensure every request reach the time limit prescribed by the system. With the increasing amount and the complexity of data stored in database sysytem, the real-time performance of Real-time database will be dropped. How to improve the overall performance of real-time database has became the study focus of the researchers. The index is one of the commonly used method to improve database performance. Generally, real-time database(RTDBS) expects to treat main memory database (MMDB) as the underlying support to improve the real-time performance. So I/O of external memory will not be "bottleneck" any more in MMDB. The goal of designing algorithm will be transferred to efficiently employing main memory and CPU. The index of tranditional disk database can’t satisfy powerful performance in both storaging and employing and accessing main memory. Aiming at above problem, designing an index structure which have the modern characteristics of main memory data become the study foundation and focus of the real-time database systems.Classical index mechanism is mainly sort to three kinds:one of them is Hash table-based index mechanism being that data is random organized; Another is based on query tree being that the data is order organized;Final is the hybrid index mechanism hybrid-HT being that the characteristics of HASH-table and query-tree is compound, After analysis of these traditional indexing mechanism in the memory environment has its own advantages and disadvantages. Thus to design a suitable real-time database index mechanism will have a prominent significance.This paper is based on The technical characteristics of the T tree and red-black tree data structure, the greatest degree to improve the real-time performance of real-time database. according to T-tree need to constantly execute the balance rotation operation, when system frequent execution the operations of the system node insert and delete. which lead to greatly reduce the efficiency of the T-tree. In view of the above, this paper propose a new kind of RB-T tree data structure algorithm model based on red-black tree balancing mechanism,Resarch it’s data structures and algorithms, and research the details introduction of design ideas and implementation process and get the following achievements:(1) Research the concept of real-time database and related technologies, including real-time database architecture, memory database, real-time transaction processing scheduling and concurrency control.(2) Research several common index of structure, focus on the strengths and weaknesses in real-time database. Including arrays, hash indexes, B-tree, T-tree and hybrid-HT index.(3) Research the characteristics of the red-black tree data structure and efficient balance principle mechanism.(4) Propose a new kind of RB-T tree data structure algorithm model based on red-black tree balancing mechanism.which is the combination of a red-black tree balance principle and the T-tree node structure.(5) Do the performance analysis and comparison experimental testing. Use an experiment way to validate and improve the theory.This paper has some creative achievements which are based on the previous results:Propose a new kind of RB-T tree data structure algorithm model based on red-black tree balancing mechanism.which is the combination of a red-black tree balance principle and the T-tree node structure. Taking into account the two factors of time cost and space costs, in order to save storage resource and reduce the cost of time.