唐山建设集团网站,做网站贵么,个人社区网站备案,外贸怎么做公司网站索引就是排好序的数据结构#xff0c;可以帮助我们快速的查找到数据#xff0c;那么底层的数据到底是如何存储的呢#xff1f;
为什么InnoDB 用的是Btree 存储结构#xff1f;
大家可以看看这个可视化的网站 数据结构和算法的可视化工具 可以看到数据结构里面有链表可以帮助我们快速的查找到数据那么底层的数据到底是如何存储的呢
为什么InnoDB 用的是Btree 存储结构
大家可以看看这个可视化的网站 数据结构和算法的可视化工具 可以看到数据结构里面有链表二叉树AVL红黑树HashB tree Btree等等可以点击进入每个数据结构的可视化页面玩一玩看看插入时数据是怎么样排序的
1.二叉查找树Binary Search Trees
二叉树的特点是左边节点比右边节点小每个叶子节点下的子节点最多只能有2个每次插入都会先比较根节点小的往左边大的往右边。
缺点 由于只能有2个叶子节点所以数据量大的时候树的层级会非常高而且当插入的数据都是有序的如下图就会造成斜树这样就退化成有序链表了
2.平衡搜索二叉树AVL trees
解决了斜树的问题每次插入是时候节点会进行旋转左小右大减少了树的高度非叶子节点最多拥有2个叶子节点同时树的左右2边层级 相差不会大于1
右旋LL当想左边节的左子节点点插入数据例如插入1086的时候为了保持树的平衡会把10节点进行右旋试树能够平衡 左旋RR当想右边节的右子节点点插入数据例如插入101214的时候为了保持树的平衡会把10节点进行左旋试树能够平衡 缺点 虽然解决了斜树的问题但是还是会造成树的层级太高每个叶子节点只能有2个子节点查询的时候会造成IO次数太多
3.红黑树Red-Black Trees 网上有大牛总结了个顺口溜根节点必黑新增是红色只能黑连黑不能红连红 爸叔通红就变色爸红叔黑就旋转哪边黑往哪边转
缺点 红黑树的缺点是每个叶子节点只能有2个子节点查询的时候会造成IO次数太多同时树的层级会非常高
红黑树和AVL树的区别
红黑树不是完全平衡不会像AVL那样要求左右2边节点的 绝对值差不大于1它只要求部分达到平衡但是提出了为节点增加颜色红黑是用非严格的平衡来换取增删节点时候旋转次数的降低任何不平衡都会在三次旋转之内解决。AVL是完全平衡在增加或者删除节点的时候旋转的次数比红黑树要多。左右2边节点的 绝对值差不大于1。由于是完全平衡所有查询效率要比红黑树高复咋情况下就是如有删除节点树要回复平衡红黑树的复衡效率更高因为最多只需要旋转3次就能回复平衡而AVL树可能会旋转多次效率更低在实际运用中如果搜索的次数远远大于插入和删除那么选择AVL因为查询效率更高如果搜索插入删除次数几乎差不多应该选择红黑树因为维护效率更高。
4.Hash
Hash实际上是散列函数它可以帮助我们大幅提升检索数据的效率这是因为 Hash 只需要一步就可以找到对应的取值算法复杂度为 O(1)。Hash 算法是通过某种确定性的算法比如 MD5、SHA1、SHA2、SHA3
采用 Hash 进行检索效率非常高例如查 id 100的数据基本上一次检索就可以找到数据而 B 树需要自顶向下依次查找多次访问节点才能找到数据中间需要多次 I/O 操作从效率来说 Hash 比 B 树更快。但是hash 有很多缺点
缺点
Hash 索引不能进行范围查询例如id 100就无法匹配索引Hash 索引不支持最左匹配原则例如有联合索引 a_b_c_indexabc3个字段Hash 索引在计算Hash 值的时候是将abc3个字段合并后再一起计算 Hash 值不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时联合索引无法匹配Hash 索引不支持 ORDER BY 排序当数据量很大时hash冲突的几率也会很是大造成hash碰撞
5.B tree多路平衡查找树
上面讲到的树有个共同的缺点就是每个叶子节点只能有2个子节点这样的话都会造成树的层级太高IO效率太低。
B-tree 利用了磁盘块的特性进行构建的树。每个磁盘块一个节点每个节点包含了很关键字。把树的节点关键字增多后树的层级比原来的二叉树少了这样就变成了N叉树并且每个节点保存key和value和data这样的存储方式的好处就是只要查询到对应数据的键值就直接返回data大大提高了查询效率减少数据查找的次数和复杂度
缺点 这样的存储结构有个缺点就是由于每个节点都保存了key-value-data那么一旦这个data的数据量大的话例如这个数据有1k10k或者更多那么一个磁盘块默认16KB就无法保存这么多节点了因为空间是有限的保存不了的话就会生成子节点这样的话树的高度又增加了磁盘IO又多了于是B树进行优化就有了B树
6.Btree
B树和 B树最大的不同是非叶子节点只储存key和value信息没有datadata 只保存在叶子节点上。这样做的好处是一个磁盘块可以存更多的节点因为不需要存data了树的高度就更矮了IO次数更低。
而且所有的叶子节点都是有序的双向链表所有数据是按照顺序排列的这样做的好处是范围查找排序查找分组查找的效率更高了举个例子例如查 23 id 52区间范围的数据只需要找到23的这个数据再通过有序链表找到52就可以快速的返回范围数据减少了IO次数提高查询效率
InnoDb的索引数据模型
在 InnoDB 中表都是根据主键顺序以索引的形式存放的这种存储方式的表称为索引组织表。又因为前面我们提到的InnoDB 使用了 B 树索引模型所以数据都是存储在 B 树中的。每一个索引在 InnoDB 里面对应一棵 B 树。 从图中不难看出根据叶子节点的内容索引类型分为主键索引和非主键索引。主键索引的叶子节点存的是整行数据。在 InnoDB 里主键索引也被称为聚簇索引clustered index。非主键索引的叶子节点内容是主键的值。在 InnoDB 里非主键索引也被称为二级索引secondary index。
主键索引和非主键索引的查询区别
如果语句是 select * from T where ID500即主键查询方式则只需要搜索 ID 这棵 B 树 如果语句是 select * from T where k5即普通索引查询方式则需要先搜索 k 索引树得到 ID 的值为 500再到 ID 索引树搜索一次。这个过程称为回表。也就是说基于非主键索引的查询需要多扫描一棵索引树。因此我们在应用中应该尽量使用主键查询。
索引维护
B 树为了维护索引有序性在插入新值的时候需要做必要的维护索引的每一页存放的是索引如果新添加一个索引的话这个索引素在的页内容满的话就需要新增一页这时候会引起索引的移动到新的也上影响性能 除了性能外索引页分裂操作还影响数据页的利用率。原本放在一个页的数据现在分到两个页中整体空间利用率降低大约 50%。要求建表语句里一定要有自增主键。当然事无绝对我们来分析一下哪些场景下应该使用自增主键而哪些场景下不应该也就是说自增主键的插入数据模式正符合了我们前面提到的递增插入的场景。每次插入一条新记录都是追加操作都不涉及到挪动其他记录也不会触发叶子节点的分裂。而有业务逻辑的字段做主键则往往不容易保证有序插入这样写数据成本相对较高。除了考虑性能外我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段比如字符串类型的身份证号那应该用身份证号做主键还是用自增字段做主键呢由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键那么每个二级索引的叶子节点占用约 20 个字节而如果用整型做主键则只要 4 个字节如果是长整型bigint则是 8 个字节。显然主键长度越小普通索引的叶子节点就越小普通索引占用的空间也就越小所以从性能和存储空间方面考量自增主键往往是更合理的选择。 有没有什么场景适合用业务字段直接做主键的呢还是有的。比如有些业务的场景需求是这样的**只有一个索引该索引必须是唯一索引。你一定看出来了这就是典型的 KV 场景。**由于没有其他索引所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则直接将这个索引设置为主键可以避免每次查询需要搜索两棵树。
7.写在最后
总结了这么多如果你还是不明白为什么要用Btree做存储结构那就再反复的学习吧
