• 展开微博窗口
  • QQ:365182575
  • 微信:cighsen
  • 展开分类目录
Nearnet

什么是btree?什么是hash?这两者有什么区别

我们以MySQL为例,来说明btree索引算法和hash索引算法。首先,我们先了解一下索引,以及btree和hash是什么。

索引原理

索引用来快速寻找特定的数据值,如果没有索引,查询时需要遍历整张表。原理大概是这样:

  1. 把创建了索引的列内容排序
  2. 排序结果生成倒排表
  3. 在倒排表内容上拼上数据地址
  4. 在查询时,先找到倒排表内容,再取出地址,最后找到数据

一、btree索引算法

  1. InnoDB存储引擎默认的索引就是btree。
  2. 节点保存索引,而不是数据。所有的数据都保存在叶子节点,叶子节点不单保存数据,还包含指向数据指针,而且按照数据自小到大顺序链接。(这里说的是b+tree)
  3. 数据的插入、删除只在叶子节点进行。(这里说的是b+tree)

btree有两种,一种是btree,还有一种是b+tree。数据库中说的b+tree一般说的是b+tree。这两种有什么区别呢?

  1. btree所有节点都是放索引和数据,而b+tree只在叶子节点放数据和索引,非叶子节点只存放索引。
  2. btree叶子节点相互独立,b+tree叶子节点有一条链相连。
  3. btree可以实现把热点数据放在离根节点进的节点,重复多次查询热数据更高效。
  4. b+tree,一次读取,在内存页获取更多的索引,更快缩小范围。
  5. 全局数据遍历,b+tree只要找到最小节点,然后通过链进行顺序遍历。而btree需要每层遍历。

二、hash索引算法

数据通过hash算法转换成定长的哈希值,将哈希值与数据的行指针存入hash表中对应的位置,如果哈希值相同,在对应的hash中以链表形式存储。这里的原理可以参考hashmap的put方法内部实现原理。

btree与hash区别:

  • btree可以用作范围查询,比如>,>=,<,<=和between,除去通配符开头查询。而hash只能用作对等查询。(这是因为使用hash建立的索引,它的顺序与原顺序无法保持一致。btree都是左节点<父节点<右节点。)
  • hash一次定位数据,btree总是从根到叶子节点,所以hash检索效率高。
  • hash不支持使用索引排序。
  • hash不支持模糊查询以及最左前缀匹配。
  • hash一定要回表查询数据,btree的聚簇索引可以不用回表索引。
  • hash等值查询效率不一定比btree高。当哈希冲突很大,就会影响效率,而btree所有查询都是从根到叶子节点。

基于这些情况,数据库通常使用btree索引算法。

码字很辛苦,转载请注明来自NAERENET《什么是btree?什么是hash?这两者有什么区别》