“树:B+树”的版本间差异
跳到导航
跳到搜索
(建立内容为“category:数据结构 == 关于 ==”的新页面) |
无编辑摘要 |
||
第2行: | 第2行: | ||
== 关于 == | == 关于 == | ||
B+树 是 [http://wiki.eijux.com/%E6%A0%91%EF%BC%9AB%E6%A0%91 B树] 的一种变形形式,也是一种'''多路搜索树''',但查询性能更好。 | |||
* B+树(B+-tree)操作模拟:[https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html] | |||
== 定义、结构、特点 == | |||
B+树 特点是:能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。 | |||
=== 定义 === | |||
基础定义与 [http://wiki.eijux.com/%E6%A0%91%EF%BC%9AB%E6%A0%91 B树] 基本等价(包括关键字及子树的个数要求等)。 | |||
'''不同点:'''“关键字个数”与“子节点个数(子树个数)”,有两种不同的定义: | |||
# “'''关键字个数 = 子节点个数'''”,如下:【Mysql B+树实现】 | |||
## 【非终端节点(内部节点)包含其子树中的最大关键字】 | |||
##: [[File:B+树:“关键字个数 = 子节点个数”【非终端节点包含其子树中的最大关键字】.png|600px]] | |||
## 【非终端节点(内部节点)包含其子树中的最小关键字】 | |||
##: [[File:B+树:“关键字个数 = 子节点个数”【非终端节点包含其子树中的最小关键字】.png|600px]] | |||
# “'''关键字个数 = 子节点个数 - 1'''”,如下:【同 B树】 | |||
#* 【父节点存有右孩子的第一个元素的索引】 | |||
#: [[File:B+树:“关键字个数 = 子节点个数 - 1”【父节点存有右孩子的第一个元素的索引】.png|600px]] | |||
=== 结构 === | |||
B+树有两种类型的节点:'''内部结点'''(即:非叶子节点,也称“索引结点”)和'''叶子结点''': | |||
* '''内部节点不存储数据,只存储索引,数据都存储在叶子节点'''。 | |||
* 所有结点(包括内部节点和叶子节点)中的 key 都按照从小到大的顺序排列。 | |||
*: 对于内部结点中的一个 key,左树中的所有 key 都小于它,右子树中的 key 都大于等于它。 | |||
* '''每个叶子结点都存有相邻叶子结点的指针'''。 | |||
* '''父节点存有右孩子的第一个元素的索引'''。【“关键字个数 = 子节点个数 - 1”时】 | |||
: [[File:B+树:典型结构.png|600px]] | |||
=== 特点【相比于 B树】 === | |||
# 层级更少:B+树中间节点不保存数据,所以每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;【B+树:'''叶子结点以上各层仅作为索引使用'''】 | |||
# 查询速度稳定:B+树所有关键字数据地址都存在叶子节点上,导致每次查找的次数都相同,所以查询速度更稳定;【B+树:'''所有关键字都在叶子结点出现'''】 | |||
#* B树搜索有可能在非叶子结点结束。 | |||
# 天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在范围查找时更方便,缓存的命中率更高。【B+树:'''叶子节点链表已有序'''】 | |||
# 全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。 | |||
#* B树需要通过中序遍历获取。 | |||
== 操作 == | |||
=== 查询 === | |||
=== 插入 === | |||
=== 删除 === | |||
== 应用 == | |||
=== MyISAM === | |||
=== InnoDB === | |||
=== MySQL采用B+树原因 === | |||
=== 关于聚簇索引与非聚簇索引 === |
2021年4月23日 (五) 02:02的版本
关于
B+树 是 B树 的一种变形形式,也是一种多路搜索树,但查询性能更好。
- B+树(B+-tree)操作模拟:https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
定义、结构、特点
B+树 特点是:能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。
定义
基础定义与 B树 基本等价(包括关键字及子树的个数要求等)。
不同点:“关键字个数”与“子节点个数(子树个数)”,有两种不同的定义:
- “关键字个数 = 子节点个数”,如下:【Mysql B+树实现】
- “关键字个数 = 子节点个数 - 1”,如下:【同 B树】
- 【父节点存有右孩子的第一个元素的索引】
结构
B+树有两种类型的节点:内部结点(即:非叶子节点,也称“索引结点”)和叶子结点:
- 内部节点不存储数据,只存储索引,数据都存储在叶子节点。
- 所有结点(包括内部节点和叶子节点)中的 key 都按照从小到大的顺序排列。
- 对于内部结点中的一个 key,左树中的所有 key 都小于它,右子树中的 key 都大于等于它。
- 每个叶子结点都存有相邻叶子结点的指针。
- 父节点存有右孩子的第一个元素的索引。【“关键字个数 = 子节点个数 - 1”时】
特点【相比于 B树】
- 层级更少:B+树中间节点不保存数据,所以每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;【B+树:叶子结点以上各层仅作为索引使用】
- 查询速度稳定:B+树所有关键字数据地址都存在叶子节点上,导致每次查找的次数都相同,所以查询速度更稳定;【B+树:所有关键字都在叶子结点出现】
- B树搜索有可能在非叶子结点结束。
- 天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在范围查找时更方便,缓存的命中率更高。【B+树:叶子节点链表已有序】
- 全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。
- B树需要通过中序遍历获取。