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

摘要

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

传统的数据库系统比如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对应的叶子结点。