中国河北建设银行官网招聘网站,网站域名查询工具,做网站与全网营销搜索推广排名优化,企业网站建设网页设计1.索引是什么东西#xff1f;
索引就是一个数据结构#xff0c;我们把表中的记录用一个适合高效查找的数据结构来表示#xff0c;目的就是让查询变得更高效。
2.它到底怎么运作的#xff1f;
这个问题就说来话长了#xff0c;且听我慢慢道来#xff1a;
在mysql中使用…1.索引是什么东西
索引就是一个数据结构我们把表中的记录用一个适合高效查找的数据结构来表示目的就是让查询变得更高效。
2.它到底怎么运作的
这个问题就说来话长了且听我慢慢道来
在mysql中使用最广泛的数据引擎是InnoDB 引擎它里面用的是 B 树索引。
我们重点分析一下这个索引的原理
要想理解B树索引要先从 二叉查找树平衡二叉树和 B 树说起因为B树索引就是由他们演化而来
什么是二叉查找树 满足这样条件的就叫二叉查找树
每个节点左边节点的值都小于该节点右边节点的值都大于该节点没有值相等的节点最顶端的节点也就是“45”被称为根节点。
二叉查找树的查找过程
若根结点的值等于查找的值成功
否则若小于根结点的值递归查左子树也就是根节点左边的所有节点形成的树
若大于根结点的值递归查右子树也就是根节点右边所有节点形成的树。
假设用二叉查找树创建book表的索引 索引如下
图一 此处的bid为主键每个节点存储了主键的值和该条记录的内容。
如果我要查找bid为6的图书的信息则先用6和根节点的主键值7比较发现比7小
然后6再和7左边的节点5比较发现比5大找到5右边的节点6找到了取出6对应的记录行的值ee.
总共经历了3次比较如果扫描全表需要经过5次比较。 什么是平衡二叉树
如果索引是这样
图二 想要找到主键键值为9的记录就需要6次比较索引的优势完全体现不出来。
为什么会这样原因就在于这棵树太高了如果能想办法把它变得矮一点胖一点就完美了。于是平衡二叉树闪亮登场
平衡二叉树首先也是一个二叉树需要满足二叉树的所有条件然后有所改进规定了左右子树的高度差不能超过1如果插入数据导致高度差超过了1则自动进行调整回复到平衡状态。这也是平衡二叉树名字的由来。
图一就是一颗平衡二叉树图二根节点的左子树高度为0右子树高度为5高度差是5超过了1所以不是一颗平衡二叉树。
平衡二叉树查找效率要高于二叉树。 什么是B树
由前面的推导我们可以看出要想查找比较的次数最少必须想办法降低树形结构的高度不管是二叉树还是平衡二叉树每个节点最多只能有两个子节点这就注定了它的高度受限于子节点的个数于是B树横空出世. 从上图可以看到B树的节点可以不止两个子节点这样的好处就是树可以变得又矮又胖矮胖的树是索引的最爱用它做索引可以降低磁盘的IO.
B树中的每个节点根据实际情况可以包含大量的键值数据和指针上图所示为一个3阶的B树
每点占用一个磁盘块的磁盘空个节间一个节点上有两个升序排序的键值和三个指向子树根节点的指针指针存储的是子节点所在磁盘块的地址。两个键值划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例键值为17和35P1指针指向的子树的数据范围为小于17P2指针指向的子树的数据范围为17~35P3指针指向的子树的数据范围为大于35。
模拟查找关键字29的过程
根据根节点找到磁盘块1读入内存。【磁盘I/O操作第1次】
比较关键字29在区间17,35找到磁盘块1的指针P2。
根据P2指针找到磁盘块3读入内存。【磁盘I/O操作第2次】
比较关键字29在区间26,30找到磁盘块3的指针P2。
根据P2指针找到磁盘块8读入内存。【磁盘I/O操作第3次】
在磁盘块8中的关键字列表中找到关键字29。
分析上面过程发现需要3次磁盘I/O操作和3次内存查找操作。由于内存中的键值是一个有序表结构可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B树查找效率的决定因素。 什么是B树
想想还有没有可能进一步优化在B树中每个节点的内容由三部分组成键值指针数据而磁盘块的容量是有限的并不是每次读取磁盘块都会取出里面的数据只是在最后一次读取的时候才会取出里面的数据能不能将数据只存储在叶子节点里面非叶子节点只存储键值和指针呢这样就能最大化的利用磁盘块空间一个磁盘块也就能存更多的东西了没错B树就是这么干的 假设在非叶子节点不存数据以后每个节点可以存储4个键值和指针就变成了上图的B树
B树相对于B树有几点不同
非叶子节点只存储键值和指针。所有叶子节点之间都有一个链指针。数据记录都存放在叶子节点中。
在B树中因为叶子节点的键值是按顺序排列的所以进行键值的范围查找效率非常高。
在B树中由于一个节点存储了更多的键值和指针所以同样多的内容可以降低树的高度减少磁盘io次数从而提高效率。
数据库的索引分为聚集索引和非聚集索引innoDb存储引擎中的聚集索引表中的数据按主键的顺序存放它实际上就是按主键构建的一个B树叶子节点存放的是数据行记录。所以数据库中的数据实际上是索引的一部分。由于实际的数据页只能按照一个顺序存放所以每张表聚集索引只能有一个。
非聚集索引的叶子节点中存放的是键值和主键值所以通过非聚集索引需要先查找到主键值然后通过聚集索引查询到具体的数据因此非聚集索引的效率要低于聚集索引。非聚集索引并不会影响到数据的存储顺序所以非聚集索引可以存在多个。
