Research And Design Of Storage Organization And Index On Main Memory Database

Since Nineteen eighties,with the memory price continuing to decline and thememory chips’ integrationbecoming higher and higher, all the data or the greater partof the data of the database stored in the memory has completely become feasible,theresearch and application of main memory database(MMDB) begins to spring upstep by step.In the real time and high concurrency application area,MMDB shows aquicker data access which the disk database can not provide,but beacause of the latertime the research and application of MMDB began,a great many design ideas betweenMMDB and disk database are not in accordance.As a result of the difference storagemedium between memory and disk,the data structure、algorithm、query strategy、indexstructure and so on fit in disk database could not be fit in MMDB any more.This article takes MMDB technology as the research direction, focusing on thestorage organization and index structrue,paying special attention to cache and TLB.In the area of storage organization, it gives a deep a analysis of N-Array storagestructrue which is widely used in today’s MMDB,then it points out the N-Arraystorage structrue’s deficiency: the poor cache utilization rate.At last it gives ananother improved storage structrue which uses the idea of discrete storage structure:ateach memory page,the property of the businness table stored by different section.Dueto this practice,the same property values’ storage region can be centralized,thus at theproperty queries,the improved storage structure can provider a better cache utilization.At the index structure area, Reviewing the study process of index structure inmain memory database,from T-tree to fervent various cache sensitive trees.In thestudy of cache sensitive tree, it gives a deep a analysis of CSS tree,CSB+tree and HTtree,pointing out each tree’s strengths and weaknesses,giving out its suit use case.Replacements cost in CSS tree are too high, CSB+tree only considers cache miss andignores the TLB miss.In HT tree,designing the leaf node as hash barrel,the height oftree is cut down so as to the less TLB miss. In the enlightenment of HT tree,it thearticle gives a schedule to improve CSB+tree, the schedule pays attention to cache atthe same time by expanding tree node capacity to cut down the tree height. Comparedwith CSB+tree,the improved CSB+tree increases the partition and index in each treenode.In the end,the articale gives the query algorithm and insertion algorithm aboutthe improved CSB+tree.At last,it gives out an experiment of cache miss and TLBmiss between CSB+tree and the improved CSB+tree.