B树和hash

写道

关系型数据库的索引大多采用B/B+树来作为存储结构，而全文检索的搜索引擎则主要采用Hash来作为索引的存储结构，这两类系统的算法都比较成熟了，为什么它们要在各自的应用环境下采用这两种数据结构来存储索引。
我个人的理解是：
数据库系统库表比较多，讲究的是灵活，尤其是在空间上的flexible很重要，而B/B+树在扩展上具有较好的空间优势（当表中数据行比较少的时候，其索引也比较小，比较灵活且节省空间），当然其查询速度在在O(logN)级别上也算是比较高了。
而搜索引擎对查询速度要求很高，所以Hash是查询速度最快的一种索引数据结构，但是它是牺牲了空间的代价，因为动态Hash一直是一个比较难的问题，所以开始为了保证较合适的填充因子，所以不得不开一个比较大的空间来存储索引，此时数据内容的条数可能并不是很多。