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

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

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

2、ndex）：InnoDB存储引擎（2）非聚集索引（non-clusteredindex）：MyISAM存储引擎逻辑分类（重点）:（1）普通索引或者单列索引（2）唯一索引（3）主键索引（4）组合索引磁盘IO与预读磁盘IO：磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2=4.17ms；传输时间指的是

3、从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17=9ms左右，听起来还挺不错的，但要知道一台500-MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。磁盘IO与预读预读：考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而且把相邻的数据也都读取到内存缓冲区内，因为局当计算机访问一个地

4、址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。部预读性原理告诉我们，具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B-tree及其变种B+tree。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结

5、构，就是索引。MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。什么是索引索引是一种允许直接访问数据表中某一数据行的树型结构，为了提高查询效率而引入，是独立于表的对象，可以存放在与表不同的表空间（TABLESPACE）中。索引记录中存有索引关键字和指向表中数据的指针（地址）。对索引进行的I/O操作比对表进行操作要少很多。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。B+tree索引的结构7索引的本质目前大部分数据库系统及文件系统都采用B-T

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

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

8、没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。B+树性质