Tide-tree: A self-tuning indexing scheme for hybrid storage system
Tide-tree: A self-tuning indexing scheme for hybrid storage system
复制标题
Tide-tree：一种混合存储系统自调整索引方案
DOI：
10.1007/s11280-016-0426-9
复制
发表时间：
2017
影响因子：
3.7
通讯作者：
Li Bohan
中科院分区：
文献类型：
--
作者：
Wang Sheng;Qin Xiaolin;Bao Zhifeng;Li Bohan
主存储器索引是在 RAM 足够大以容纳数据的假设下构建的。由于主存的波动性大、单价较高，SSD、HDD等副存下的指数被广泛使用。然而，对主存的I/O操作仍然是查询效率的瓶颈。在本文中，我们提出了一种用于基于 RAM/磁盘的混合存储系统的自调整索引方案，称为 Tide-tree。 Tide-tree旨在克服主存和基于磁盘的索引所面临的障碍，像潮水一样表现，实现空间和性能的双赢，并且对运行环境具有自适应性。特别是，Tide-tree基于存储感知高效地自适应地分层树结构，并应用有效的自调整算法将各种节点动态加载到主存中。我们采用内存映射技术解决主存索引持久化问题，提高数据同步和指针翻译的效率。为了进一步增强潮汐树的独立性，我们采用索引头和层地址表来管理整个索引。通过索引头，提出了三种高效的操作，即索引重建、索引加载和范围搜索。我们进行了大量的实验，将 Tide-tree 与几种最先进的索引进行比较，结果验证了 Tide-tree 的高效性、可重用性和稳定性。
Main memory index is built with the assumption that the RAM is sufficiently large to hold data. Due to the volatility and high unit price of main memory, indices under secondary memory such as SSD and HDD are widely used. However, the I/O operation with main memory is still the bottleneck for query efficiency. In this paper, we propose a self-tuning indexing scheme called Tide-tree for RAM/Disk-based hybrid storage system. Tide-tree aims to overcome the obstacles main memory and disk-based indices face, and performs like the tide to achieve a double-win in space and performance, which is self-adaptive with respect to the running environment. Particularly, Tide-tree delaminates the tree structure adaptively with high efficiency based on storage sense, and applies an effective self-tuning algorithm to dynamically load various nodes into main memory. We employ memory mapping technology to solve the persistent problem of main memory index, and improves the efficiency of data synchronism and pointer translation. To further enhance the independence of Tide-tree, we employ theindex headand the level address table to manage the whole index. With theindex head, three efficient operations are proposed, namely index rebuild, index load and range search. We have conducted extensive experiments to compare the Tide-tree with several state-of-the-art indices, and the results have validated the high efficiency, reusability and stability of Tide-tree.