Research And Improvement Of The Index Mechanism Of The Embedded Main Memory Database

Nowadays,embedded database system has been widely applied in all social areas as a kernal technology of mobile computation,information appliance and electronic commerce.It has many fuctions,for example, public information service,real_time data collection,position_related search and so on.Based on the mature database technology,the embedded database system implements the storage,operation and management of data in accordance with the special features of embedded devices.The transactions processed in the embedded database are usually real_time transactions and the correctness of transaction dispatch depends on the capacity of highly efficient process and predict.Because the input and output speed of disk is very low and the disk deferment is unpredict-able,main memory database technology is often used in the embedded database system.The efficiency of operation on database depends deeply on the index mechanism which the database adopts.Because limited storage space of main memory and low process capacity are the unique features of embedded system,the index mechanism which adapts to the embedded database should comsume storage space as little as possible and further promote the speed of data operation at the same time.The existing index mechanism of main memory database such as T-tree,T*-tree,T-tail tree,hybrid-TH,hash cannot meet the time and space demand of embedded system simultaneously,so it appears important to work out a new index mechanism that has better time and space performance.Based on the traditional hybrid index mechanism-hybrid-TH,a new mechanism in accordance with the special features of embedded database is brought up by this paper.The new mechanism called H-T*-tail not only has the advantage of using little storage space but also promotes the speed of search and modification in no small measure.This thesis firstly introduces the embedded database and the main memory database technology in totality.It then elaborates in detail the algorithms of basic operations on traditional index mechanism, including T-tree,T*-tree,T-tail tree and hybrid-TH.Afterwards,it analyzes the time and space properties of hybrid-TH mechanism in the theoretical degree and points out the drawbacks of it.Next it focuses on discussing the new index mechanism-H-T*-tail and the new tree structure adopted by H-T*-tail-T*-tail.It then analyzes the time and space performance of the new index mechanism in the theoretical level.Lastly,it has verified the excellent time and space performance of H-T*-tail through a series ofexperiments which make comparisions between the two hybrid index mechanism-hybrid-TH and H-T*-tail.The new index mechanism has subsequent characteristics: -$■ Each element is stored only once,so reduces the consumption ofstorage space;?$■ The elements which have the same hash address are arranged in a T*-tail atom tree;4" Scatters all elements to many atom trees through hash table and dataoperations are carreded out on atom trees,so has shrinked the scope ofoperation;■^ Has shifted the burden of search from hash table to T*-tail atom treesand adopts the improved search algorithm,so has improved the searchperformance;"$■ When the internal nodes in T*-tail atom trees have underflowed afterbeing taken element away,it is decided by its balance factor thatwhich node to move element from,precursor or successor.This stategyhas greatly decreased the times of rotation that is needed to keepbalance;■$? Hash table doesn't store keys of records actually,it only has thefunction of locating the position of the corresponding atom tree;■$■ Don't need to set up the relationship between the hash structure andthe tree structure,so has saved the expenses on preserving andpromoted the performance of modification.