存储系统中内存索引结构的选择

摘要

随着最近几十年来服务器主存容量的增加,即使是大型的事务数据库也能把索引全部放到主存中,当索引数据都在内存中时,索引的性能也就越来越重要。

传统的数据库系统比如mysql一般用B+树作为自己的索引,B+树能够有效减少磁盘IO次数,支持范围查询,但在纯内存环境下,它的性能表现并不太好,特别是B+树是通过key的比较来找节点的,当比较结果产生分支预测失败时,会引起CPU stall。

哈希表是另外一个流行的内存数据结构,和查找树O(logn)的查找时间相比,哈希表只有O(1)的查找时间。尽管如此,哈希表有两个缺陷,一个是哈希表不能支持范围查询,二是哈希表的rehash非常慢可能会造成严重的性能抖动。如果说业务不需要支持范围查询又容量恒定的话,哈希表是最快的索引结构。

第三种数据结构被称为radix tree,或者前缀树,trie等。和二叉树不同,key不会直接保存在节点中,而是由节点在树中的位置决定。radix tree把一个完整的key转变成了字符的序列,每个节点都对应一个特定的字符,每个字符都有可能指向任意一个字符。在radix tree中查找一个key就像查字典一样。从根节点开始每个字符都可以找到一个对应的节点,依次查找key的所有字符就找到了key对应的叶子结点。

欢迎在评论区写下你对这篇文章的看法。

评论

首页 - Wiki
Copyright © 2011-2024 iteam. Current version is 2.137.3. UTC+08:00, 2024-11-26 03:42
浙ICP备14020137号-1 $访客地图$