Embedded Database Indexing Mechanism

With the gradual maturity of 3G technology and research and development of B3G technology, Wireless transmission capacity is growing. Users can use smartphone, PDA and other mobile equipments to connect to the network through wireless technology. They can use mobile devices to access network resources at any time. People use embedded database to manage the information in many embedded device. But in embedded systems, the storage capacity is very limited. There is a focus research topic that how to make the best use of limited storage and improve the utilization of storage space in the embedded database.Currently, the most embedded database systems use B+ tree indexing mechanism. It has advantage of high efficiency and being able to process operations on the records of B+ trees randomly and sequentially. It can maintain the dynamic balance of the tree. However, the B+ tree indexing mechanism has a fatal disadvantage for wasting storage space capacity in the embedded systems. The statistic shows that B+ tree indexing mechanism guarantee only about 50% storage utilization.When one node is split, the database system use an additional "overflow page" to store the overflow keyword, this can defer the node split and improve the utilization of storage space, it is the ideas of overflow technology. Research shows that the store space utilization of overflow technology has more 20% to 30% than B+tree indexing mechanism.The main task of this dissertation is to study and achieve an indexing mechanism in the embedded database system. It has higher utilization than B+ tree indexing mechanism. At first, The dissertation introduces some classic indexing mechanism in the embedded database and analyses their advantages and disadvantages. Then analyses the ideas of B+ tree indexing mechanism and their advantages and disadvantages. The dissertation uses a combination of B+ tree indexing mechanism and overflow technology to come at an improved indexing mechanism--B# tree indexing mechanism, then program to achieve the B# tree indexing mechanism and replace the B+ tree indexing mechanism in the open-source embedded database SQLite. At last, put SQLite to the development board of MAGICARM2410 of Zhi Yuan ltd. in Guangzhou after repeating test the system, then build the platform and program with tcl script language. Under the same conditions and time, the dissertation tests SQLite with B+ tree and B# tree indexing mechanism respectively and analyses the reasons for the disparity in the test results, the experimental results show that the B# tree algorithm can attain higher storage utilization at the expense of a little more execution time than B+ tree algorithm, even inserted in a little record, it consumes considerable time with the B+ tree indexing mechanism, but its store space utilization even come to 76%. The result has some advantages for making the best use of the limited storage space for equipment in the embedded database system which request for a little real-time performance, such as intelligent mobile phones use embedded database system to manage users' information.