最新MySql索引原理解析-马龙组ppt课件.ppt

《最新MySql索引原理解析-马龙组ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、MySql索引原理解析-马龙组工作分配孔敢：数据库索引PPT整体的构造和思路陈诗华：展示讲解数据库的索引李佳：数据库结构的分类(对应不同的数据库存储引擎)刘伟洁：物理分类周文兵：逻辑分类、PPT制作索引的分类索引的分类大致可以从逻辑分类，物理分类以及数据结构分类这三个方面来阐述：数据结构分类：（1）B+树索引(O(log(n)))（底层重点）（2）hash索引（3）FULLTEXT索引（4）R-Tree索引物理分类：（对应于不同的数据库存储引擎）：（1）聚集索引（clusteredindex）：InnoDB存储引擎（2）非聚集索引（non-clusteredinde

2、x）：MyISAM存储引擎逻辑分类（重点）:（1）普通索引或者单列索引（2）唯一索引（3）主键索引（4）组合索引什么是索引索引是一种允许直接访问数据表中某一数据行的树型结构，为了提高查询效率而引入，是独立于表的对象，可以存放在与表不同的表空间（TABLESPACE）中。索引记录中存有索引关键字和指向表中数据的指针（地址）。对索引进行的I/O操作比对表进行操作要少很多。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。B+tree索引的结构7索引的本质目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。這里主要介绍使用

3、较为广泛的B+TreeB+树详解左边的图中，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针。我们假设一个盘块刚好只能存储一个结点，那么左图中一个结点就表示一个盘块，其子树指针就是指向另一个盘块的地址。现在我们来模拟查找文件29的过程：根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。B+树查找过程根据算法我们发现：17<29<35，因此我们找到指针p2。根据p2指针，我们定位到磁盘块3，并将其中的信息导入内

4、存。【磁盘IO操作2次】此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

5、B+树性质1.通过上面的分析，我们知道IO次数取决于b+树的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m=磁盘块的大小/数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表

6、。B+树性质2.当b+树的数据项是复合的数据结构，比如：(name,age,sex)的时候，b+树是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺

7、失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了，这个是非常重要的性质，即索引的最左匹配特性。带有顺序访问指针的B+Tree一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。B+tree原理解析一