根据前两篇的铺垫,今天我们可以去具体看看索引的知识了。索引的知识以mysql为基本,虽然本人项目使用的PGSql....
B,B+树的性能考量:
我们知道数据库的文件都是存储在磁盘中,那么IO操作就是评价一个索引结构好坏的最好标准。如果这个索引是顺序结构,那么查询一个数据的时间复杂度就是O(N),数据少还行,到百万,千万级别的时候,查询一次也要O(N),就意味着N次IO,要命。
而B树则不然,根据第一章的学习,访问B树中最下方的一个节点数据,只发生了3次IO操作(查找了3个高度的节点,最终定位到当前节点中)。而更巧妙的地方在于,数据库系统在设计的时候,一个节点的大小就等于一页的大小(关于页的概念,此文不分析),这就意味着一次IO就能一个节点完全载入其中。
1.B树的时间复杂度是一个渐进式的O(h)=O(log d(N) )。h是树高,d是度,也就是分支的数目,N是总记录数。
2.B树的高度 h=log(m+1)N(不确定,但是估计关系差不多是如此),假设 数据总量是N,每个节点的数据项是m。由此可知N一定的情况下,m越大,h就越小。而m = 节点的大小/数据项的大小。而节点的大小刚刚说过,大小基本就是确定的,因此如果数据项空间越小,则m就越多,m越多,树的高度h就越小,查找更有利。
这也就是索引字段为什么要小的缘故,小了的话节点的数据项就越多,高度就越小。而B+树内把真是的数据又放在了叶子节点中,非叶子节点中只存放了索引的数据,保证了数据项尽可能的多。保证树的高度。
Mysql中存储引擎的索引实现:
Mysql有两种存储引擎,MyISAM和InnoDB,InnoDB常听说,好像用的也是最多的,MyISAM不常听说。
1.MyISAM使用的是B+树作为引擎,下图展示的是主键索引的示意图:
可以看见索引文件和数据记录其实是分开来的,索引文件里存储的其实是数据记录的地址。
2.MyISAM辅助索引和主键索引类似,但是辅助索引的key可以重复,这是和主键不同的地方。
3.InnoDB的索引实现也是B+树,但是具体的方式确不一样。
3.1第一点,数据文件本身就是索引文件,这一点怎么理解呢?还记得B+树的叶子节点存储了具体数据嘛,在InnoDB里,叶子节点存储的树真正的数据值,而不是MyISAM里存储的是地址。索引的key就是数据表的主键。InnoDB主索引的示意图如下,可以看见叶节点包含了完整的数据记录,这种索引也叫做聚集索引。因为InnoDB的数据文件本身要按照主键聚集,所以必须要有主键。如果没有显示指定,则Mysql会自动选择可以唯一标识的数据列作为主键,如果不存在这种列,则Mysql自动为InnoDB生成一个隐含字段,占位6字节,长整型。
3.2InnoDB辅助索引也和MyISAM不同,辅助索引里面存储的是数据的主键而不是地址,可以这么说InnoDB的辅助索引最终还是要依赖主键索引来实现。下图是以名字为索引的单列索引B+树结构:
3.3辅助索引里面有一个比较特殊的索引叫覆盖索引。它奇特在哪边呢?从3.2我们知道辅助索引的data区域其实存储的是主键的地址,需要通过主键进行再一次定位访问到具体的数据。那么假设:
select uage,uname from user where uage = 12;
如果我们建立的是复合索引(uage,uname)的话,上面一条语句会用到索引,而且能够直接返回出ucard和uname,而不需要再去进行主键定位的操作,这就是特别之处。所以这个复合索引其实可以说成是一种覆盖索引。
那么复合索引的B+树结构是怎么样的呢?这里我们假设user表结构中的联合索引是(age,name,address)。下图不能确认是否是正确的,只是通过参考不同的文章总结出的自己的假设。
通过这个结构我们可以看见,在叶子节点中存储的数据是age,name,address的值(假设这些数据都是按照顺序排列好的,图中是随意写的),那么如果我们只想要这几个值的话,都不需要再进行主键定位查询了,提高了一些效率。
小结:
InnoDB的聚集索引是按照主键搜索,是最高效的,辅助索引需要走两次索引,首先查询辅助索引得到主键,再跟进主键查询获得记录。
问题1:不建议主键字段过长:原因上面第2点也讲过一些,过长会造成数据项空间变大,每个节点数据项数目变少,高度增加。
另外我们发现辅助索引的data域记录的也是主键,因此简介造成辅助索引变大,查询困难。
问题2:非单调字段:如果不是单调字段的话,会造成B+树不断的调整,十分低效,上一篇分析过插入和删除。使用自增字段的话会保持一个相对稳定的顺序。
---------------------
作者:刘二郎
来源:CSDN
原文:https://blog.csdn.net/qq_32924343/article/details/80199977
版权声明:本文为博主原创文章,转载请附上博文链接!
相关推荐
BAT面试深入理解Mysql索引底层数据结构与算法_1
BAT面试_深入理解Mysql索引底层数据结构与算法_4
诸葛_BAT面试_深入理解Mysql索引底层数据结构与算法_3
BAT面试_深入理解Mysql索引底层数据结构与算法_5
BAT面试_深入理解Mysql索引底层数据结构与算法_6
BAT面试_深入理解Mysql索引底层数据结构与算法_7
BAT面试_深入理解Mysql索引底层数据结构与算法_8
BAT面试_深入理解Mysql索引底层数据结构与算法_9
诸葛_BAT面试_深入理解Mysql索引底层数据结构与算法_2
大概了解 Oracle 索引底层的数据结构,从而更好地理解 Oracle 索引对增、删、改、查的性能。B-树(B-tree) 非索引的结构能满足所有需要,但自平衡的 B-树索引结构更能优化在大数据集上检索的性能。每个 B-树节点...
本资料“深入理解MySQL索引底层”将帮助我们深入探究MySQL索引的工作原理、类型以及优化策略。 一、索引概述 索引是一种数据结构,它为数据库表中的列提供了快速访问路径。通过索引,数据库可以快速定位到特定记录...
4-1【回放】深入理解Mysql索引底层数据结构与算法.mp4
这个“解析NTFS底层结构”的教程是初学者理解NTFS内部工作原理的宝贵资源。以下是对NTFS的一些关键知识点的详细阐述: 1. **MFT(Master File Table)主文件表**:NTFS的核心组件,它存储了所有文件和目录的元数据...
"NTFS底层结构与原理" NTFS(New Technology File System)是 Windows NT 引入的新型文件系统,相比 FAT 磁盘格式,它提供了更高的安全性、更好的性能和更大的存储容量。NTFS 的底层结构复杂,内容繁多,本文将对 ...
17. **B+树索引底层结构**:B+树是一种自平衡的查找树,所有叶子节点都在同一层,有利于范围查询,是数据库索引常用的数据结构。 18. **B+树叶子节点链表**:B+树的叶子节点之间通过指针链接,形成双向链表,便于...
17. **B+树作为索引底层结构**: B+树是一种高效的数据索引结构,所有数据都在叶子节点,非叶子节点只用来索引,适合磁盘I/O操作。 18. **B+树叶子节点链表**: B+树的叶子节点通过指针连接成双向链表,便于区间...
Mysql表索引优化与底层数据结构深入剖析
树形结构使用 B 树或者 B+ 树的结构,使用层级查找,中间节点保存一定顺序范围的词典项目存储在哪个子树中,最底层的叶子节点存储单词的地址信息。 搜索引擎索引数据结构和算法是搜索引擎的核心组件,它们定义了...