Based On The Hybrid Dynamic Hash Embedded Database Index

With the development of embedded and electronic technology, theperformance of the key components in embedded systems (such asmicroprocessors and flash memory) is constantly improving, and its price has inreducing. It makes embedded devices could handle more and more complextasks in a lower cost. However, using the simple file system to manage data isunable to meet the data management of the embedded systems, which core taskis processing data. Therefore, the embedded database is designed for solve thisquestion.The SQLite which is open source database software was adopted as theinstance object of the embedded database. An efficient hybrid indexingmechanism combined with the features of dynamic hash and the TC tree wasproposed. And some appropriate experiment was implemented to verify that theefficiency of the mixed index mechanism in the aspects of retrieval and insertionoperations.First of all, the architecture and index mechanism of SQLite were Analyzedin this paper. Secondly, the research was focused on the characteristic of typicaldynamic hash, Tree index and some hybrid index. Thirdly, an unbalanced treeindex——TC tree was proposed in this paper, which was combined with thefeature of T tree and red black tree. The question that the operating performancewas reduced could be solved, resulted from the frequent adjustment operationcaused by strict equilibrium conditions of T tree. Besides, a new dynamic hashwas designed combined with the characteristic of extendible hashing and linearhashing and named it as IDH——Incremental dynamic hash. The bucket in IDHcould be split immediately when bucket overflow occurred and only expanded adirectory unit once splitting. The number of directory extension in an adjustmentoperation was only related to the location of the overflow bucket. In addition, itwas proposed a new hybrid index mechanism——IDH-TC, which used the IDHas an upper apart for data bucket positioning and used TC tree to organize the data bucket.The Simulation experiment verifies the efficiency of insertion and retrievaloperations in the hybrid index mechanism in the case of random data. The timecomplexity of embedded database retrieval almost is O(1) in this hybridindexing mechanism. And the Insert operations was presented cyclicalfluctuations trend of slow growth dips affected by the storage utilization.Compared with T-tree, the TC-tree had a better efficiency in insert operation,and Retrieve and delete operations performance was similar. Then this paperwas focused on the three dynamic hashing algorithms including of linear hash,extendible hash and incremental dynamic hash. It analyzed the influence on theindex size from split condition consist of bucket overflow and storage utilizationand data skew. The result of experiment shows that with the data increasing thedynamic hash with bucket overflow as the split condition have a bigger indexsize and less overflow bucket than the dynamic hash with storage utilization asthe split condition. Besides, the impact of data skew on the linear hash andextendible hash is same with the storage utilization as the split condition. Withthe bucket overflow as split condition, the more data in the back-end of index,the less index size for the linear hash and the more index size for the improveddynamic hash.In conclusion, the hybrid indexing mechanism IDH-TC proposed in thispaper is a highly efficient embedded database indexing mechanism. And it canimprove the performance of the retrieval and insertion operation.