MySQL数据库,详解索引原理(四)
b+树
先看个b+树结构图:
b+树的特征
1. 每个结点⾄多有m个⼦⼥
2. 除根结点外,每个结点⾄少有[m/2]个⼦⼥,根结点⾄少有两个⼦⼥
3. 有k个⼦⼥的结点必有k个关键字
4. ⽗节点中持有访问⼦节点的指针
5. ⽗节点的关键字在⼦节点中都存在(如上⾯的1/20/35在每层都存在),要么是最⼩值,要么是最⼤值,如果节点中关键字是升序的⽅式,⽗节点的关键字是⼦节点的最⼩值
6. 最底层的节点是叶⼦节点
7. 除叶⼦节点之外,其他节点不保存数据,只保存关键字和指针8. 叶⼦节点包含了所有数据的关键字以及data,叶⼦节点之间⽤链表连接起来,可以⾮
常⽅便的⽀持范围查找b+树与b-树的⼏点不同
1. b+树中⼀个节点如果有k个关键字,最多可以包含k个⼦节点(k个关键字对应k个指针);⽽b-树对应k+1个⼦节点(多了⼀个指向⼦节点的指针)
2. b+树除叶⼦节点之外其他节点值存储关键字和指向⼦节点的指针,⽽b-树还存储了数据,这样同样⼤⼩情况下,b+树可以存储更多的关键字
3. b+树叶⼦节点中存储了所有关键字及data,并且多个节点⽤链表连接,从上图中看⼦节点中数据从左向右是有序的,这样快速可以⽀撑范围查找(先定位范围的最⼤值和
最⼩值,然后⼦节点中依靠链表遍历范围数据)
B-Tree和B+Tree该如何选择?
1. B-Tree因为⾮叶⼦结点也保存具体数据,所以在查找某个关键字的时候找到即可返回。⽽B+Tree所有的数据都在叶⼦结点,每次查找都得到叶⼦结点。所以在同样⾼度的B-Tree和B+Tree中,B-Tree查找某个关键字的效率更⾼。
2. 由于B+Tree所有的数据都在叶⼦结点,并且结点之间有指针连接,在找⼤于某个关键字或者⼩于某个关键字的数据的时候,B+Tree只需要找到该关键字然后沿着链表遍历就可以了,⽽B-Tree还需要遍历该关键字结点的根结点去搜索。
3. 由于B-Tree的每个结点(这⾥的结点可以理解为⼀个数据页)都存储主键+实际数据,⽽B+Tree⾮叶⼦结点只存储关键字信息,⽽每个页的⼤⼩有限是有限的,所以同⼀页能存储的B-Tree的数据会⽐B+Tree存储的更少。这样同样总量的数据,B-Tree的深度会更⼤,增⼤查询时的磁盘I/O次数,进⽽影响查询效率。Mysql的存储引擎和索引mysql内部索引是由不同的引擎实现的,主要说⼀下InnoDB和MyISAM这两种引擎中的索引,这两种引擎中的索引都是使⽤b+树的结构来存储的。
InnoDB中的索引
Innodb中有2种索引:主键索引(聚集索引)、辅助索引(⾮聚集索引)。
主键索引:每个表只有⼀个主键索引,b+树结构,叶⼦节点同时保存了主键的值也数据记录,其他节点只存储主键的值。
辅助索引:每个表可以有多个,b+树结构,叶⼦节点保存了索引字段的值以及主键的值,其他节点只存储索引指端的值。
MyISAM引擎中的索引
B+树结构,MyISM使⽤的是⾮聚簇索引,⾮聚簇索引的两棵B+树看上去没什么不同,节点的结构完全⼀致只是存储的内容不同⽽已,主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独⽴的地⽅,这两颗B+树的叶⼦节点都使⽤⼀个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。由于索引树是独⽴的,通过辅助键检索⽆需访问主键的索引树。
如下图:为了更形象说明这两种索引的区别,我们假想⼀个表存储了4⾏数据。其中Id作为主索引,Name作为辅助索引,图中清晰的显⽰了聚簇索引和⾮聚簇索引的差异。
相关文章
- 从本体论开始说起——运营商关系图谱的构建及应用
- 如何成为一名数据科学家?
- 从未见过的堂兄杀了人,你的DNA是关键证据
- 20个安全可靠的免费数据源,各领域数据任你挑
- 20个安全可靠的免费数据源,各领域数据任你挑
- 阿里云李飞飞:All in Cloud时代,云原生数据库优势明显
- 基于Hadoop生态系统的一高性能数据存储格式CarbonData(性能篇)
- 大数据告诉你:10年漫威,到底有多少角色
- TigerGraph:实时图数据库助力金融风控升级
- Splunk利用Splunk Connected Experiences和Splunk Business Flow 扩大数据访问
- 大数据开发常见的9种数据分析手段
- 以免在景区看人,我爬了5W条全国景点门票数据...
- 【实战解析】基于HBase的大数据存储在京东的应用场景
- 数据科学家告诉你哪些计算机科学书籍是你应该看的
- Kafka作为大数据的核心技术,你了解多少?
- Spring Boot 整合 Redis 实现缓存操作
- 大数据学习必须掌握的五大核心技术有哪些?
- 基于Antlr在Apache Flink中实现监控规则DSL化的探索实践
- 甲骨文再次被Gartner评为分析型数据管理解决方案魔力象限领导者
- 爬取吴亦凡微博102118条转发数据,扒一扒流量的真假