Embedded Real-time Memory Database To Achieve

Due to the unpredictably of disk I/O, main memory database technology is the best choice of embedded real-time database system. Because of real-time restrict and differences between main memory and disk storage speciality, there are also many distinctions in design and realization between tradition database and real-time main memory database. And many mechanisms need to be researched and redesigned.Since the current main memory database index structures do not make effective use of cache, this dissertation analyzes a digital tree technology, which is called Judy. Judy has many advantages, such as fast access, predictable height, adjustable node size, minimal number of memory accesses, etc. But Judy is poor in range queries. After a visit to a node, Judy has to backtrack through the upper nodes, and then traverse to find the next leaf node. This will cause many cache line fills, and the time overhead is too much.In order to improve the capacity in range queries, a new index structure, which is called J#-tree, is proposed in this dissertation. Compared with Judy, J#-tree adds a precursor pointer and a successor pointer into every leaf node, pointing to the precursor node and the successor node, respectively. While executing a range query in a J#-tree, the precursor or the successor pointer can quickly position to the next query node. It can eliminate the time overhead of backtracking, and cause a significant reduction of the cache line fills.As J#-tree has fine spatial and temporal properties, this dissertation designs an embedded real-time main memory database, which is based on J#-tree and called DBSql. It adopts the modular design method, and the users can adjust it to their needs. DBSql provides two interfaces are provided to users. One is the familiar SQL interface, and the other one is the API functions. DBSql can be embedded in applications as a function library. This can reduce the cost of interprocess communication.DBSql takes J#-tree as the memory organization and indexing mechanism. And other mechanisms in DBSql are based on the J#-tree. As the node data structure of J#-tree depends on the number of keys under the node, the size of each node is quiet different. In order to save memory space, DBSql allocates memory by the size of node.As an embedded real-time main memory database, the concurrency control and the recovery mechanism of DBSql are very important. DBSql obeys the two-phase locking protocol according to priority, to meet the needs of real-time transactions. In order to maintain the consistency of the database, DBSql doesn't allow the update results to be written into the actual database until the transaction commits, and the fuzzy checkpointing is adopted. Based on these strategies, the recovery mechanism of DBSql is in effective protection.According to the experimental results, DBSql provides good performance. So it is suitable to be an embedded real-time main memory database.