黄小华的个人网站
熬过无人问津的日子才有诗和远方!
MySql B树

读这一篇文章是可以参照上一篇磁盘的博文一起看

MySql使用的B+Tree原理

数据库索引为何采用BTree?

红黑树等数据结构也可以用来实现索引 效果不如B+树

1.红黑树节点存储数据少,地址不连续,不适合磁盘存取的数据,不适合存储大量数据,I/O浪费太大,读取到的资源浪费也大
2.HashMap用红黑树是因为HashMap是存在内存中不是磁盘 无需进行磁盘I/O
内存不能存储大量数据
文件系统及数据库系统普遍采用B-/B+Tree作为索引结构
索引利于快速找到数据,索引本身很大,不可能全部存储内存,因此需要以索引文件的形式存储磁盘
磁盘I/O存取的消耗要高内存读取几百倍,因此索引的结构组织尽量减少查找过程中的磁盘I/O操作

几种数据结构的总结

二叉查找树,红黑树,B -Tree, B+Tree 的区别:

二叉查找树是高效查找树的基础,

红黑树:内存查找高效树,不适合大数据量也不适合磁盘存储的。具体的分析就是。I0浪费以及读取资源浪费
还有就是树的深度会很大。适合一些底层系统做内存运算.
B-Tree:可 以认为是B+Tree过度。只需要知道BTree就可以 B+Tree:最适合大数据的磁盘索引,经典的MySq1,所有的数据都存在叶子节点。其他都是索引,
增加了系统的稳定性以及遍历以及查找效率
不同:关键字和Key值。数据存储的地方,双向链表。
M阶:这个由磁盘的页面大小决定,磁盘快和页内存都是4KB。我们的节点数也就是我们的M值应该要尽可能的跟他一样。
1 0. 75的原则HashMap

BTree 索引的性能分析

1.巧妙地利用磁盘预读原理,将一个树节点大小设为一个页(4k),使得每个节点只需要一次IO 就可以完全载入
2.通常B-/+Tree的高(h)为3,而度(d每个节点的子树数)会很大,度越大索引性能越好,

B树

逻辑约束:
1.度-节点的数据存储个数(每个节点孩子节点的个数)
2.叶子节点深度相同
3.叶子节点的指针为空
4.节点中的数据key从左到右递增排序
QQ图片20200402015703.jpg

B+树

逻辑约束:
1.非叶子节点不能存储Data,只能存储key(为了让一个节点存储更多key,增大度)
2.叶子节点不存储指针
3.顺序访问指针,提高区间访问性能(块间有指针相连)可以支持范围查找等
QQ图片20200402015722.jpg

InnoDB

存储引擎InnoDB,data域存储完整的数据逻辑。聚集型,数据文件本身就是索引文件

主键索引(聚集索引)

InnoDB引擎保证必有主键索引,有主键就通过主键列来索引数据。没有定义主键,InnoDB则会选择一个唯一的非空索引列代替。
如果没有这样的索引,会选择第一个非空的唯一索引代替,如果没有非空唯一索引,Innodb会隐式定义一个6字节的rowid主键
来作为聚集索引。Innodb只聚集在同一个页面中的记录,包含相邻键值的页面可能会相距甚远。(物理位置)
一般建议使用自增主键索引
1.自增主键 pk 业务主键(身份证)
2.自增主键,每次 insert 操作会按顺序添加到当前索引节点的后续位置,当一页写满,自动开辟一个新的页。
3.非自增主键(身份证号或学号),由于每次插入主键的值都近似随机,因此每次新记录都会查到现有索引页的中间位置,不得不产生一次数据移动
QQ图片20200402015730.jpg

非主键索引

QQ图片20200402015735.jpg
非主键索引结点不存储数据只存主键id
1.保持数据一致性(某个键的索引改了其他索引数据没改到)
2.减少数据冗余

MYISAM

3.存储引擎MylSAM 索引方式,key 域存储主键,data域存储值得地址,非聚集,索引文件和数据文件是分离的
节点中只存地址,分为不同的文件
QQ图片20200402022024.jpg

SQL语句在MYSQL里究竟是如何运行?

例 select* from user where uid=100
1.没有索引:链表从头到尾遍历,直到找到id=100
2.索引:BTree(效率高) 类似二分法去找

B树的构建过程

B树的一个节点度的多少由磁盘块的大小决定,大约为一个磁盘块的75%
M度的Btree的几个重要特性:
1.结点最多含有m颗子树,m-1个关键字(m>=2);
2.除根结点和叶子结点外,其它每个结点至少有ceil(m / 2)个子节点,ceil为上取整;
3.若根节点不是叶子节点,则至少有两颗子树。
举例:
创建一颗度为5的B树
3 14 7 1 8 5 11 17 13 6 23 12 20 26 4 16 18 24 25 19 根据Btree特性,5阶则一个磁盘空间最多有5个指针(存的查找路径 ),4个关键字(mysql存的数据)。那么具体的插入如下所示: QQ截图20200403230642.png
插入8时发现空间不够,这时会出现分裂,把中间节点拿出,大于中间节点的在右边,小于的在左边
QQ截图20200403230951.png
插入13:需要注意,此时Btree又会进行一次分裂,这分裂需要注意下13会移到根节点,得到以下树
QQ截图20200403231121.png
就这样一直插入 最后会得到以下的树

QQ截图20200403231132.png

B+树

性质:
1、每个结点有多少子节点就有多少键(这里不同于B树)
2、根结点要么为空 要么独根,否则至少有两个子节点
3、叶子节点的高度相同
4、每个结点键的数量至少要是一个节点容量的一半,除2向上取整
QQ截图20200403231925.png 所有数据存在叶子节点,每个叶子节点有指针相连,每个叶子节点的最后一个索引的键在非叶子节点上有一个索引, B+树不同于B树 它的插入是从叶子节点开始插入的不是根结点 从下向上插