广州市提取住房补贴建设银行网站,wordpress设置首页只有一张图片,做网站 找风投,全国论坛网站建设先来一段有莫的对话#xff1a;前几天下班回到家后正在处理一个白天没解决的bug#xff0c;厕所突然传来对象的声音#xff1a;对象#xff1a;xx#xff0c;你有《时间简史》吗#xff1f;我#xff1a;我去#xff01;妹子#xff0c;你这啥癖好啊#xff0c;我有时…先来一段有莫的对话前几天下班回到家后正在处理一个白天没解决的bug厕所突然传来对象的声音对象xx你有《时间简史》吗我我去妹子你这啥癖好啊我有时间也不会去捡屎啊对象...人家说的是霍金的科普著作《时间简史》是一本书啦我哦那我没有...对象人家想看诶你明天帮我去图书馆借一本吧...我我明天还要改...对象你是不是不爱我了分手我我一大早就去~第二天一大早我就到了图书馆刚进门就看到一个索引牌标识着不同楼层的功能这样我很快能定位到我要找的目标所在的楼层了。我到楼上后又看到每排的书架上又对书的分类进行了细分这样我能更快的定位到我要找的书具体在哪个书架并且每个楼层都有一台查询终端输入书名就能查到对应的唯一标识“索书号”类似于P159-49/164这样的一个编码书架上的书都是按照这个编码进行排序的有了这个编码再去对应的书架上很快就能找到对应的书在书架的具体位置了。不到十分钟我就从图书馆借好书出来了。这么大的图书馆我为什么能在这么短的时间内找到我要的书如果这些书是杂乱无章的堆放或者没有任何标识的放在书架我还能这么快的找到吗这不禁让我想到了我们开发中用到的数据库图书馆的书就类似我们数据表中的数据楼层索引牌、书架分类标识、索书号就类似我们查找数据的索引。那我们常用的数据库的索引底层的一个数据结构是什么样的呢想到这里我又回到图书馆借了一本《数据库从入门到放弃》要了解数据库索引的底层原理我们就得先了解一种叫树的数据结构而树中很经典的一种数据结构就是二叉树所以下面我们就从二叉树到平衡二叉树再到B-树最后到B树来一步一步了解数据库索引底层的原理二叉树(Binary Search Trees)二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树有如下特性1、每个结点都包含一个元素以及n个子树这里0≤n≤2。2、左子树和右子树是有顺序的次序不能任意颠倒。左子树的值要小于父结点右子树的值要大于父结点。光看概念有点枯燥假设我们现在有这样一组数[35 27 48 12 29 38 55]顺序的插入到一个数的结构中步骤如下好了这就是一棵二叉树啦我们能看到经通过一系列的插入操作之后原本无序的一组数已经变成一个有序的结构了并且这个树满足了上面提到的两个二叉树的特性但是如果同样是上面那一组数我们自己升序排列后再插入也就是说按照[12 27 29 35 38 48 55]的顺序插入会怎么样呢由于是升序插入新插入的数据总是比已存在的结点数据都要大所以每次都会往结点的右边插入最终导致这棵树严重偏科上图就是最坏的情况也就是一棵树退化为一个线性链表了这样查找效率自然就低了完全没有发挥树的优势了呢为了较大发挥二叉树的查找效率让二叉树不再偏科保持各科平衡所以有了平衡二叉树平衡二叉树 (AVL Trees)平衡二叉树是一种特殊的二叉树所以他也满足前面说到的二叉树的两个特性同时还有一个特性它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。大家也看到了前面[35 27 48 12 29 38 55]插入完成后的图其实就已经是一颗平衡二叉树啦。那如果按照[12 27 29 35 38 48 55]的顺序插入一颗平衡二叉树会怎么样呢我们看看插入以及平衡的过程这棵树始终满足平衡二叉树的几个特性而保持平衡这样我们的树也不会退化为线性链表了我们需要查找一个数的时候就能沿着树根一直往下找这样的查找效率和二分法查找是一样的呢一颗平衡二叉树能容纳多少的结点呢这跟树的高度是有关系的假设树的高度为h那每一层最多容纳的结点数量为2^(n-1)整棵树最多容纳节点数为2^02^12^2...2^(h-1)。这样计算100w数据树的高度大概在20左右那也就是说从有着100w条数据的平衡二叉树中找一个数据最坏的情况下需要20次查找。如果是内存操作效率也是很高的但是我们数据库中的数据基本都是放在磁盘中的每读取一个二叉树的结点就是一次磁盘IO这样我们找一条数据如果要经过20次磁盘的IO那性能就成了一个很大的问题了那我们是不是可以把这棵树压缩一下让每一层能够容纳更多的节点呢虽然我矮但是我胖啊...B-Tree这颗矮胖的树就是B-Tree注意中间是杠精的杠而不是减所以也不要读成B减Tree了~那B-Tree有哪些特性呢一棵m阶的B-Tree有如下特性1、每个结点最多m个子结点。2、除了根结点和叶子结点外每个结点最少有m/2(向上取整)个子结点。3、如果根结点不是叶子结点那根结点至少包含两个子结点。4、所有的叶子结点都位于同一层。5、每个结点都包含k个元素(关键字)这里m/2≤k6、每个节点中的元素(关键字)从小到大排列。7、每个元素(关键字)字左结点的值都小于或等于该元素(关键字)。右结点的值都大于或等于该元素(关键字)。是不是感觉跟丈母娘张口问你要彩礼一样列一堆的条件而且每一条都让你很懵逼下面我们以一个[0,1,2,3,4,5,6,7]的数组插入一颗3阶的B-Tree为例将所有的条件都串起来你就明白了那么你是否对B-Tree的几点特性都清晰了呢在二叉树中每个结点只有一个元素。但是在B-Tree中每个结点都可能包含多个元素并且非叶子结点在元素的左右都有指向子结点的指针。如果需要查找一个元素那流程是怎么样的呢我们看下图如果我们要在下面的B-Tree中找到关键字24那流程如下从这个流程我们能看出B-Tree的查询效率好像也并不比平衡二叉树高。但是查询所经过的结点数量要少很多也就意味着要少很多次的磁盘IO这对性能的提升是很大的。前面对B-Tree操作的图我们能看出来元素就是类似1、2、3这样的数值但是数据库的数据都是一条条的数据如果某个数据库以B-Tree的数据结构存储数据那数据怎么存放的呢我们看下一张图普通的B-Tree的结点中元素就是一个个的数字。但是上图中我们把元素部分拆分成了key-data的形式key就是数据的主键data就是具体的数据。这样我们在找一条数的时候就沿着根结点往下找就ok了效率是比较高的。BTreeBTree是在B-Tree基础上的一种优化使其更适合实现外存储索引结构。BTree与B-Tree的结构很像但是也有几个自己的特性1、所有的非叶子节点只存储关键字信息。2、所有卫星数据(具体数据)都存在叶子结点中。3、所有的叶子结点中包含了全部元素的信息。4、所有叶子节点之间都有一个链指针。如果上面B-Tree的图变成BTree那应该如下大家仔细对比于B-Tree的图能发现什么不同1、非叶子结点上已经只有key信息了满足上面第1点特性2、所有叶子结点下面都有一个data区域满足上面第2点特性3、非叶子结点的数据在叶子结点上都能找到如根结点的元素4、8在最底层的叶子结点上也能找到满足上面第3点特性4、注意图中叶子结点之间的箭头满足满足上面第4点特性B-Tree or BTree在讲这两种数据结构在数据库中的选择之前我们还需要了解的一个知识点是操作系统从磁盘读取数据到内存是以磁盘块(block)为基本单位的位于同一个磁盘块中的数据会被一次性读取出来而不是需要什么取什么。即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理 当一个数据被用到时其附近的数据也通常会马上被使用。预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块每个存储块称为一页(在许多操作系统中页得大小通常为4k)。B-Tree和BTree该如何选择呢都有哪些优劣呢1、B-Tree因为非叶子结点也保存具体数据所以在查找某个关键字的时候找到即可返回。而BTree所有的数据都在叶子结点每次查找都得到叶子结点。所以在同样高度的B-Tree和BTree中B-Tree查找某个关键字的效率更高。2、由于BTree所有的数据都在叶子结点并且结点之间有指针连接在找大于某个关键字或者小于某个关键字的数据的时候BTree只需要找到该关键字然后沿着链表遍历就可以了而B-Tree还需要遍历该关键字结点的根结点去搜索。3、由于B-Tree的每个结点(这里的结点可以理解为一个数据页)都存储主键实际数据而BTree非叶子结点只存储关键字信息而每个页的大小有限是有限的所以同一页能存储的B-Tree的数据会比BTree存储的更少。这样同样总量的数据B-Tree的深度会更大增大查询时的磁盘I/O次数进而影响查询效率。鉴于以上的比较所以在常用的关系型数据库中都是选择BTree的数据结构来存储数据下面我们以mysql的innodb存储引擎为例讲解其他类似sqlserver、oracle的原理类似innodb引擎数据存储在InnoDB存储引擎中也有页的概念默认每个页的大小为16K也就是每次读取数据时都是读取4*4k的大小假设我们现在有一个用户表我们往里面写数据这里需要注意的一点是在某个页内插入新行时为了不减少数据的移动通常是插入到当前行的后面或者是已删除行留下来的空间所以在某一个页内的数据并不是完全有序的(后面页结构部分有细讲)但是为了为了数据访问顺序性在每个记录中都有一个指向下一条记录的指针以此构成了一条单向有序链表不过在这里为了方便演示我是按顺序排列的由于数据还比较少一个页就能容下所以只有一个根结点主键和数据也都是保存在根结点(左边的数字代表主键右边名字、性别代表具体的数据)。假设我们写入10条数据之后Page1满了再写入新的数据会怎么存放呢我们继续看下图有个叫“秦寿生”的朋友来了但是Page1已经放不下数据了这时候就需要进行页分裂产生一个新的Page。在innodb中的流程是怎么样的呢1、产生新的Page2然后将Page1的内容复制到Page2。2、产生新的Page3“秦寿生”的数据放入Page3。3、原来的Page1依然作为根结点但是变成了一个不存放数据只存放索引的页并且有两个子结点Page2、Page3。这里有两个问题需要注意的是1、为什么要复制Page1为Page2而不是创建一个新的页作为根结点这样就少了一步复制的开销了如果是重新创建根结点那根结点存储的物理地址可能经常会变不利于查找。并且在innodb中根结点是会预读到内存中的所以结点的物理地址固定会比较好2、原来Page1有10条数据在插入第11条数据的时候进行裂变根据前面对B-Tree、BTree特性的了解那这至少是一颗11阶的树裂变之后每个结点的元素至少为11/25个那是不是应该页裂变之后主键1-5的数据还是在原来的页主键6-11的数据会放到新的页根结点存放主键6如果是这样的话新的页空间利用率只有50%并且会导致更为频繁的页分裂。所以innodb对这一点做了优化新的数据放入新创建的页不移动原有页面的任何记录。随着数据的不断写入这棵树也逐渐枝繁叶茂如下图每次新增数据都是将一个页写满然后新创建一个页继续写这里其实是有个隐含条件的那就是主键自增主键自增写入时新插入的数据不会影响到原有页插入效率高且页的利用率高但是如果主键是无序的或者随机的那每次的插入可能会导致原有页频繁的分裂影响插入效率降低页的利用率这也是为什么在innodb中建议设置主键自增的原因这棵树的非叶子结点上存的都是主键那如果一个表没有主键会怎么样在innodb中如果一个表没有主键那默认会找建了唯一索引的列如果也没有则会生成一个隐形的字段作为主键有数据插入那就有删除如果这个用户表频繁的插入和删除那会导致数据页产生碎片页的空间利用率低还会导致树变的“虚高”降低查询效率这可以通过索引重建来消除碎片提高查询效率innodb引擎数据查找数据插入了怎么查找呢1、找到数据所在的页。这个查找过程就跟前面说到的BTree的搜索过程是一样的从根结点开始查找一直到叶子结点。2、在页内找具体的数据。读取第1步找到的叶子结点数据到内存中然后通过分块查找的方法找到具体的数据。这跟我们在新华字典中找某个汉字是一样的先通过字典的索引定位到该汉字拼音所在的页然后到指定的页找到具体的汉字。innodb中定位到页后用了哪种策略快速查找某个主键呢这我们就需要从页结构开始了解。左边蓝色区域称为Page Directory这块区域由多个slot组成是一个稀疏索引结构即一个槽中可能属于多个记录最少属于4条记录最多属于8条记录。槽内的数据是有序存放的所以当我们寻找一条数据的时候可以先在槽中通过二分法查找到一个大致的位置。右边区域为数据区域每一个数据页中都包含多条行数据。注意看图中最上面和最下面的两条特殊的行记录Infimum和Supremum这是两个虚拟的行记录。在没有其他用户数据的时候Infimum的下一条记录的指针指向Supremum当有用户数据的时候Infimum的下一条记录的指针指向当前页中最小的用户记录当前页中最大的用户记录的下一条记录的指针指向Supremum至此整个页内的所有行记录形成一个单向链表。行记录被Page Directory逻辑的分成了多个块块与块之间是有序的也就是说“4”这个槽指向的数据块内最大的行记录的主键都要比“8”这个槽指向的数据块内最小的行记录的主键要小。但是块内部的行记录不一定有序。每个行记录的都有一个n_owned的区域(图中粉红色区域)n_owned标识这个这个块有多少条数据伪记录Infimum的n_owned值总是1记录Supremum的n_owned的取值范围为[1,8]其他用户记录n_owned的取值范围[4,8]并且只有每个块中最大的那条记录的n_owned才会有值其他的用户记录的n_owned为0。所以当我们要找主键为6的记录时先通过二分法在稀疏索引中找到对应的槽也就是Page Directory中“8”这个槽“8”这个槽指向的是该数据块中最大的记录而数据是单向链表结构所以无法逆向查找所以需要找到上一个槽即“4”这个槽然后通过“4”这个槽中最大的用户记录的指针沿着链表顺序查找到目标记录。聚集索引非聚集索引前面关于数据存储的都是演示的聚集索引的实现如果上面的用户表需要以“用户名字”建立一个非聚集索引是怎么实现的呢我们看下图非聚集索引的存储结构与前面是一样的不同的是在叶子结点的数据部分存的不再是具体的数据而数据的聚集索引的key。所以通过非聚集索引查找的过程是先找到该索引key对应的聚集索引的key然后再拿聚集索引的key到主键索引树上查找对应的数据这个过程称为回表图中的这些名字均来源于网络希望没有误伤正在看这篇文章的你~^_^innodb与MyISAM两种存储引擎对比上面包括存储和搜索都是拿的innodb引擎为例那MyISAM与innodb在存储上有啥不同呢憋缩话看图上图为MyISAM主键索引的存储结构我们能看到的不同是1、主键索引树的叶子结点的数据区域没有存放实际的数据存放的是数据记录的地址。2、数据的存储不是按主键顺序存放的按写入的顺序存放。也就是说innodb引擎数据在物理上是按主键顺序存放而MyISAM引擎数据在物理上按插入的顺序存放。并且MyISAM的叶子结点不存放数据所以非聚集索引的存储结构与聚集索引类似在使用非聚集索引查找数据的时候通过非聚集索引树就能直接找到数据的地址了不需要回表这比innodb的搜索效率会更高呢索引优化建议大家经常会在很多的文章或书中能看到一些索引的使用建议比如说1、like的模糊查询以%开头会导致索引失效。2、一个表建的索引尽量不要超过5个。3、尽量使用覆盖索引。4、尽量不要在重复数据多的列上建索引。5、。。。。。。。。。。。6、。。。。。。。。。。。很多这里就不一一列举了那看完这篇文章我们能否带着疑问去分析一下为什么要有这些建议为什么like的模糊查询以%开头会导致索引失效为什么一个表建的索引尽量不要超过5个为什么 为什么为什么相信看到这里的你再加上自己的一些思考应该有答案了吧
