为什么数据库采用B树,搜索引擎用Hash

发布网友发布时间：2022-04-08 04:35

我来回答

共2个回答

懂视网时间：2022-04-08 08:56

B+树在数据库中的应用

flyfish 2015-7-6

B+树在数据库中的应用重要是实现索引

应用方式一

ID为表的主键，利用主键建立一棵B+树
叶子结点存储记录的地址
技术分享

应用方式二

ID为表的主键，建立一棵B+树
叶子结点存储了整条记录
技术分享

B+树在数据库中的应用

标签：b+树

热心网友时间：2022-04-08 06:04

关系型数据库的索引大多采用B/B+树来作为存储结构，而全文检索的搜索引擎则主要采用Hash来作为索引的存储结构，这两类系统的算法都比较成熟了，为什么它们要在各自的应用环境下采用这两种数据结构来存储索引。

我个人的理解是：

数据库系统库表比较多，讲究的是灵活，尤其是在空间上的flexible很重要，而B/B+树在扩展上具有较好的空间优势（当表中数据行比较少的时候，其索引也比较小，比较灵活且节省空间），当然其查询速度在在O(logN)级别上也算是比较高了。

而搜索引擎对查询速度要求很高，所以Hash是查询速度最快的一种索引数据结构，但是它是牺牲了空间的代价，因为动态Hash一直是一个比较难的问题，所以开始为了保证较合适的填充因子，所以不得不开一个比较大的空间来存储索引，此时数据内容的条数可能并不是很多。