IP交换机中嵌入式内存数据库HSQL的索引优化

Optimizing Index of Embedded Main Memory Database HSQL in IP Switch

该文分析总结了当前在内存数据库中提高树索引的缓存敏感性的主要技术,设计并实现了一个具有缓存敏感性的AVL树,即CC-AVL树。CC-AVL树合理利用缓存行的大小,并构造父子节点在内存中连续存储的结构,从而使一个缓存行中包含正要访问的节点和其左孩子节点,同时使用CPU支持的数据预取技术获得右孩子节点。从而使CC-AVL树比AVL树具有更高的缓存敏感性。CC-AVL树被用于一个运行在IP交换机中的嵌入式内存数据库HSQL中。

This paper describes recent main techniques of cache-conscious index in detail.We design and implement a cache-conscious AVL tree structure,CC-AVL tree.CC-AVL trees construct a consecutive memory for a parent node and its left child node in a tree of which a cache line is composed.It utilizes the prefetching instructions provided by CPU to prefetch the right node.Therefore,CC-AVL trees are more cache-conscious than AVL trees.CC-AVL trees are used in HSQL,which is an embedded main memory database used in an IP switch.