莱芜百度网站制作,软文推广产品,东莞品牌设计公司,什么是白帽seo首先要说明的是#xff0c;B-树和B树是指同一个结构#xff0c;并没有所谓的B减树#xff0c;两种树是B-树和B树。
Mysql存储结构是一个B树。
1.存储结构与索引
众所周知#xff0c;索引是关系型数据库中给数据库表中一列或多列的值排序后的存储结构#xff0c;它是一种…首先要说明的是B-树和B树是指同一个结构并没有所谓的B减树两种树是B-树和B树。
Mysql存储结构是一个B树。
1.存储结构与索引
众所周知索引是关系型数据库中给数据库表中一列或多列的值排序后的存储结构它是一种加快查询速度的数据结构常用索引结构有hash、B-Tree和BTreeMysql选用的是B树索引。
1Hash
hash是基于哈希表完成索引存储哈希表特性是数据存放是散列的。
优点
等值查询快通过hash值直接定位到具体的数据。
缺点
范围查询效率低表中的数据是无序数据在日常开发中通常需要范围查询该情况下hash需要一个一个查找后合并返回hash表在使用的时会将所有数据加载到内存比较消耗内存hash算法不好会出现hash碰撞的情况哈希索引只包含哈希值和行指针而不存储字段值索引不能使用索引中的值来避免读取行哈希索引不支持部分列匹配查找哈希索引是使用索引列的全部内容来计算哈希值
2B-Tree
a
B树(或B-树、B_树)它是一种m阶平衡多叉树。当m取2时便是二叉搜索树其中m指的是一个结点最多有多少个孩子结点。 对于m阶B树其具有如下性质
根结点至少有两个子女每个结点的值的个数为 1 n m所有的叶子结点都位于同一层除根结点以外的所有结点不包括叶子结点的孩子正好是值个数的加1每个结点中的值都按照从小到大的顺序排列每个值的左子树中的所有的值都小于它而右子树中的所有的值都大于它。
如下图所示 上图为3阶B树在实际应用中的B树的阶数m都非常大通常大于100所以即使存储大量的数据B树的高度仍然比较小这有利于树的插入删除。在数据库中我们将B树和B树作为索引结构可以加快查询速速。 B树的插入 如果插入的结点只有一个数值直接在该结点插入即可。例如在上图中插入9则直接在10结点前面插入9即可。但如果插入44此时便需要通过结点的向上分裂来完成插入。 插入44 发现此结点有3个值不满足3阶B树因此要进行分裂将中间的40向上结点移动 分裂后此B树变成了4阶B树不满足3阶B树条件原因是40移动到上结点所致因此继续向上结点移动将50移动到上节点 此时发现又出现3个值的结点继续进行分裂 此时便满足条件完成。
B树的删除按照插入的方法反过来操作即可即父结点(如果不符合父结点大于左结点小于右结点的条件则与上层父节点位置调换直到符合条件为止)不断下移合并直到符合条件为止。
b
B树在磁盘存储中 B-Tree特点
所有键值数据分布在整棵树各个节点中搜索有可能在非节点结束在关键字全集内查找类似二分查找所有叶子节点都在同一层并且以升序排列
3BTree
a
在B树中只有叶子节点存储数据其它中间结点全部是索引。在数据库的聚集索引中叶子节点直接包含数据库中某一行数据。在非聚集索引中叶子节点带有指向数据库行的指针。
B树是B树的一种变体有着比B树更高的查询性能B树和B树除了有一些共同特点外还有一些新的特点
有k个子树的中间结点包含有k个元素B树中是k-1个元素每个元素不保存数据只用来索引所有数据都保存在叶子节点。所有的叶子结点中包含了全部元素的信息及指向含这些元素记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。所有的中间结点元素都同时存在于子节点在子节点元素中是最大或最小元素。下面使用数值来表示一棵B树 可以看出B树的每个结点的最大或最小元素都出现在下一个结点的首或尾
B树的查找 B树的查找有两种方式从最小值进行顺序查找从根结点开始进行随机查找。在查找时若非终端结点上的关键值等于给定值并不终止而是继续向下直到叶子结点因为叶子结点才存数据。因此在B树中不管查找成功与否每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。 由于B树的数据都存储在叶子结点中分支结点均为索引方便扫库只需要扫一遍叶子结点即可但是B树因为其分支结点同样存储着数据我们要找到具体的数据需要进行一次中序遍历按序来扫所以B树更加适合在区间查询的情况所以通常B树用于数据库索引而B树则常用于文件索引。
B树的插入 假设我们要向上图插入0发现没有破坏B树结构直接在12结点处插入即可。
如果在结点的中间插入并破坏了B树的结构
但是如果我们要插入12则发现破坏了B树的结构则 分裂破坏了结构的结点并将12移到上结点 插入完毕。
如果在端点处插入并破坏了B树的结构
假如插入16 分裂后父结点要配合子结点的端点值 删除操作只需将插入操作进行反向操作即可。读者可以想想如何删除16。
B数的优势
单一节点存储更多的元素使得查询的IO次数更少。应用于文件系统、数据库系统所有查询都要查找到叶子节点查询性能稳定。所有叶子节点形成有序链表便于范围查询。
b
Mysql存储中 BTree 是在B-Tree的基础之上做的一种优化变化如下
BTree 非叶子节点不存放数据叶子节点存储关键字和数据非叶子节点的关键字也会沉到叶子节点并且排序叶子节点两两指针相互连接形成一个双向环形链表符合磁盘的预读特性顺序查询性能更高
Mysql为什么选择BTree Mysql官网文档中写到InnoDB索引用的是 B-tree但是底层用的是BTree。Mysql存储数据是以页为单位默认一个页可以存放16K数据。假设B-Tree和BTree都是3层深度表中每个记录为1K(假设的一般不会这么大别较真)那么三层深度的B-Tree存储 16 x 16 x 16 4096比这个数还要少因为每个页中还要存放指针和其它的数据。BTree第一、二层存放的是key假设是Long类型的主键那么第一、二层每页存放数据约为 16 x 1024 / 8 2048三层深度可以存放 2048 x 2048 x 16 6700W。MySQL查询过程是按页加载数据的每加载一页就是一次IO操作BTree进行三次IO可以查询6700W数据量。从这里也可以知道Mysql一般设置三层深度就足够了。 2.聚集索引与非聚集索引
聚集clustered索引也叫聚簇索引 定义数据行的物理顺序与列值一般是主键的那一列的逻辑顺序相同一个表中只能拥有一个聚集索引。 打个比方把数据表比作新华字典聚集索引就是拼音目录而每个字存放的页码就是实际的数据物理地址如果要查询一个“草”字我们只需要查询“草”字对应在新华字典拼音目录对应的页码就可以查询到对应的“草”字所在的位置而拼音目录对应的A-Z的字顺序和新华字典实际存储的字的顺序A-Z也是一样的如果我们中文新出了一个字拼音开头第一个是B那么他插入的时候也要按照拼音目录顺序插入到A字的后面。
如下表所示
第一列的地址表示该行数据在磁盘中的物理地址后面三列表示数据库表的真实数据其中id是主键建立了聚集索引 数据行的物理顺序与列值的顺序相同如果我们查询id比较靠后的数据那么这行数据的地址在磁盘中的物理地址也会比较靠后。而且由于物理排列方式与聚集索引的顺序相同所以只能建立一个聚集索引。 聚集索引实际存放的示意图
从上图可以看出聚集索引的好处了索引的叶子节点就是对应的数据节点MySQL的MyISAM除外此存储引擎的聚集索引和非聚集索引只多了个唯一约束其他没什么区别可以直接获取到对应的全部列的数据而非聚集索引在索引没有覆盖到对应的列的时候需要进行二次查询。因此在查询方面聚集索引的速度往往会更占优势 非聚集索引 定义该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同一个表中可以拥有多个非聚集索引。 按照上述比喻非聚集索引就像新华字典的偏旁字典存放的结构顺序与实际存放顺序不一定一致。 非聚集索引实际存放的示意图
非聚集索引的二次查询问题
非聚集索引叶节点仍然是索引节点只是有一个指针指向对应的数据块此如果使用非聚集索引查询而查询列中包含了其他该索引没有覆盖的列那么他还要进行第二次的查询查询节点上对应的数据行的数据。
如有以下表t1 以及聚集索引clustered index(id), 非聚集索引index(username)。
使用以下语句进行查询不需要进行二次查询直接就可以从非聚集索引的节点里面就可以获取到查询列的数据。
select id, username from t1 where username 小明
select username from t1 where username 小明
但是使用以下语句进行查询就需要二次的查询去获取原数据行的score
select username, score from t1 where username 小明如何解决非聚集索引的二次查询回表查询问题
复合索引覆盖索引将被查询的字段建立到联合索引里去。
建立两列以上的索引即可查询复合索引里的列的数据而不需要进行回表二次查询如index(col1, col2)执行下面的语句
select col1, col2 from t1 where col1 213;
要注意使用复合索引需要满足最左侧索引的原则也就是查询的时候如果where条件里面没有最左边的一到多列索引就不会起作用。 总结 使用聚集索引的查询效率要比非聚集索引的效率要高但是如果需要频繁去改变聚集索引的值写入性能并不高因为需要移动对应数据的物理位置。非聚集索引在查询的时候可以的话就避免二次查询这样性能会大幅提升。不是所有的表都适合建立索引只有数据量大表才适合建立索引且建立在选择性高的列上面性能会更好。下面举一个具体的例子 InnoDB聚集索引和普通索引有什么差异
InnoDB聚集索引的叶子节点存储行记录因此 InnoDB必须要有且只有一个聚集索引
1如果表定义了PK则PK就是聚集索引
2如果表没有定义PK则第一个not NULL unique列是聚集索引
3否则InnoDB会创建一个隐藏的row-id作为聚集索引
画外音所以PK查询非常快直接定位行记录。
InnoDB普通索引的叶子节点存储主键值。 画外音注意不是存储行记录头指针MyISAM的索引叶子节点存储记录指针。
举个栗子不妨设有表 t(id PK, name KEY, sex, flag);
画外音id是聚集索引name是普通索引。 表中有四条记录 1, shenjian, m, A 3, zhangsan, m, A 5, lisi, m, A 9, wangwu, f, B 两个B树索引分别如上图 1id为PK聚集索引叶子节点存储行记录 2name为KEY普通索引叶子节点存储PK值即id 既然从普通索引无法直接定位行记录那普通索引的查询过程是怎么样的呢
通常情况下需要扫码两遍索引树。 例如 1 select * from t where namelisi;
是如何执行的呢 如粉红色路径需要扫码两遍索引树
1先通过普通索引定位到主键值id5
2在通过聚集索引定位到行记录 这就是所谓的回表查询先定位主键值再定位行记录它的性能较扫一遍索引树更低。
提高效率索引覆盖如何实现索引覆盖常见的方法是将被查询的字段建立到联合索引里去。
仍是之前中的例子 1 2 3 4 5 6 create table user ( id int primary key, name varchar(20), sex varchar(5), index(name) )engineinnodb;
1. 第一个sql 1 select id,name from user where nameshenjian;
能够命中name索引索引叶子节点存储了主键id通过name的索引树即可获取id和name无需回表符合索引覆盖效率较高。
2. 第二个sql 1 select id,name,sex from user where nameshenjian;
能够命中name索引索引叶子节点存储了主键id但sex字段必须回表查询才能获取到不符合索引覆盖需要再次通过id值扫码聚集索引获取sex字段效率会降低。
如果把(name)单列索引升级为联合索引(name, sex)就不同了。 1 2 3 4 5 6 create table user ( id int primary key, name varchar(20), sex varchar(5), index(name, sex) )engineinnodb;
可以看到 1 2 3 select id,name ... where nameshenjian; select id,name,sex ... where nameshenjian;
都能够命中索引覆盖无需回表。 索引覆盖优化SQL场景
场景1全表count查询优化
关于这点的解释可以参考这里count(*)的查询 当没有非主键索引时会使用主键索引如果存在非主键索引的话会使用非主键索引如果存在多个非主键索引会使用一个最小的非主键索引其原因是在innodb中非主键索引叶子节点存储的结构是索引主键主键索引叶子节点是主键表数据。在1个page里面非主键索引可以存储更多的条目例如 对于一张表如果有1000000数据使用非主键索引扫描的page数可能是100 而使用主键索引page数可能是500此时使用非主键索引的性能会更好。同理如果存在多个非主键索引会使用一个最小的非主键索引也是为了在一个page里存储更多的数据从而减少扫描次数提高性能。 这里使用的是单字段count()查询意思差不多。 原表为
user(PK id, name, sex)
直接 1 select count(name) from user;
不能利用索引覆盖。
添加索引 1 alter table user add key(name);
就能够利用索引覆盖提效。
场景2列查询回表优化 1 select id,name,sex ... where nameshenjian;
这个例子不再赘述将单列索引(name)升级为联合索引(name, sex)即可避免回表。
场景3分页查询 1 select id,name,sex ... order by name limit 500,100;
将单列索引(name)升级为联合索引(name, sex)也可以避免回表。
最后这一段
