Research Program Based On The Optimization Of The Indexing Mechanism Of Red-black Tree Embedded Database Sqlite

With the popularity of embedded technology, embedded database hasbecome the new direction of development of database technology, it is alsowidely applied to the production and living. The SQLite database is a moremainstream product on the market. SQLite is an open source, embeddeddatabase, uses B-tree storage structure. The structure cannot meet the usersrequirement due to the increasing amount of data, an appropriate indexingmechanism becames an important aspect of the embedded database system.Based on the analysis of SQLite's system structure, working principle andindex system,this paper compare some indexing mechanism used currently,research indexing technology of embedded database and the correspondingquery processing. In order to solve the problem of B-tree inefficient processinglarge data, a scheme of the B-tree substituted by red-black tree is presented.Firstly, the paper discuss the embedded system and related technology ofembedded database in-depth, analysis system structure and indexing mechanismof a typical embedded database SQLite, focusing on the operation performanceof B-tree.Secondly, the paper research and analysis structure and performance of thered-black tree, compare red-black tree with B-tree and AVL tree. A red-blacktree is self-balancing binary search tree, each of its nodes have been"coloring"black or red, These colors node are used to detect the tree balance. Becausered-black tree only requires partially balance, it reduces the requirements ofrotation, improving the operation performance.Again, based on the above research, the paper build the SQLite databasemodel which based on the red-black tree structure. Query, insert and deleteoperations realization with C language.Finally, compare SQLite database model based on the red-black treestructure with SQLite database model based on B tree structure by a lot ofexperiments. The results final test red-black tree as an indexing mechanism ofembedded database can achieved better performance. For SQLite database, using the red-black tree can achieve the optimiz of the index mechanism.