江苏龙网

  1. 首页 > 人文 > >

为什么使用B+Tree？( 二 )


2.1 哈希索引不能满足业务需求
哈希（Hash）是一种非常快的查找方法 ， 在一般情况下这种查找的时间复杂度为O（1） ， 即一般仅需要一次查找就能定位到数据 。 在各种编程语言和数据库中应用广泛 ， 如Java ， Python ， Redis中都有使用 。
为什么使用B+Tree？
本文插图
哈希结构在单条数据的等值查询是性能非常优秀 ， 但是只能用来搜索等值的查询 ，对于范围查询 ， 模糊查询（最左前缀原则）都不支持 ， 所以不能很好的支持业务需求；所以MySQL并没有显式支持Hash索引 ， 而是根据数据的访问频次和模式自动的为热点数据页建立哈希索引 ， 称之为自适应哈希索引 。
并且由于哈希函数的随机性 ， Hash索引通常都是随机的内存访问 ， 对于缓存不友好 ， 会造成频繁的磁盘IO 。
2.2 二叉搜索树退化成链表
二叉搜索树 ， 如果左子树不为空 ， 则左子树上所有节点均小于根节点 ， 右子树节点均大于根节点；由其属性不难看出 ， 这种树非常适合数据查找 。 不过有个致命的缺点是二叉搜索树的树型取决于数据的输入顺序 ， 极端情况下会退化成链表 。
为什么使用B+Tree？
本文插图
2.3 平衡二叉搜索树过于严格
为了解决上述问题 ， 平衡二叉搜索树就诞生了 。 在保证数据顺序的基础上 ， 又能维持树型 ， 保证每个节点的左右子树高度相差不超过1 。
不过由于要维持树的平衡 ， 在插入数据时可能要进行大量的数据移动 。 平衡搜索二叉树过于严格的平衡要求 ， 导致几乎每次插入和删除节点都会破坏树的平衡性 ， 使得树的性能大打折扣 。
【为什么使用B+Tree？】
为什么使用B+Tree？
本文插图
2.4 红黑树高度过高 ， 磁盘IO次数频繁
有没有一种数据结构 ， 即能够快速查找数据 ， 又不需要频繁的调整以维持平衡呢？这时红黑树就闪亮登场了 。
红黑树和其他二叉搜索树类似 ，都是在进行插入和删除操作时通过特定操作保持二叉查找树的性质 ， 从而获得较高的查找性能 。 与之不同的是 ， 红黑树的平衡性并不像平衡搜索二叉树一样严格的同时 ， 又能保证在 ，O(log n) 时间复杂度内做查找和删除 。
红黑树通过改变节点的颜色 ， 可以有效减少节点的移动次数 ， 由于红黑树的实现比较复杂 ， 本文不再展开 ， 感兴趣的小伙伴可以去深入学习 。
为什么使用B+Tree？
本文插图
看似红黑树是一种完美的数据结构 ， 能够胜任索引的工作 。 但MySQL并未使用其作为索引的实现 ， 主要原因在于红黑树的深度过大 ， 数据检索时造成磁盘IO频繁 ， 假设一个每个节点存储在一个page中 ， 树的高度为10 ， 则每次检索可能就需要进行10次磁盘IO 。
2.5 B-Tree不支持顺序查询
B-Tree是一种自平衡的多叉搜索树 ， 一个节点可以拥有两个以上的子节点 。 适合读写相对大的数据块的存储系统 ， 例如磁盘 。
为什么使用B+Tree？
本文插图
由于MySQL索引一般都存储在内存中 ， 如果使用B-Tree作为索引的话 ， 索引和数据存储在一块 ， 分布在各个节点中；而内存资源往往比较宝贵 ， 一定内存的情况下可以存储的索引数量相对有限 ， 毕竟每条数据的大小一般远大于索引列的大小 ， 导致内存使用率不高 。
数据查询过程中往往会有顺序查询 ， 而B-Tree和红黑树对于顺序查询并不友好 。
2.6 为什么选B+Tree


推荐阅读


上一篇：IT时报20年后，网易回家了，中概股回归三问

下一篇：艾尔数码小栈全“芯”升级！首发天玑1000Plus，iQOO Z1强悍性能降维打击