Mysql索引底层数据结构

Mysql索引底层数据结构课题大纲1.索引优化面试题分析2.索引数据结构3.MyISAM和InnoDB索引实现索引优化面试题分析CREATETABLE`employees`(`id`int(11)NOTNULLAUTO_INCREMENT,`name`varchar(24)NOTNULLDEFAULT''COMMENT'姓名',`age`int(11)NOTNULLDEFAULT'0'COMMENT'年龄',`position`varchar(20)NOTNULLDEFAULT''COMMENT'职位',`hire_time`timestampNOTNULLDEFAULTCURRENT_TIMESTAMPCOMMENT'入职时间',PRIMARYKEY(`id`),KEY`idx_name_age_position`(`name`,`age`,`position`)USINGBTREE)ENGINE=InnoDBAUTO_INCREMENT=4DEFAULTCHARSET=utf8COMMENT='员工记录表';INSERTINTOemployees(name,age,position,hire_time)VALUES('LiLei',22,'manager',NOW());INSERTINTOemployees(name,age,position,hire_time)VALUES('HanMeimei',23,'dev',NOW());INSERTINTOemployees(name,age,position,hire_time)VALUES('Lucy',23,'dev',NOW());索引优化面试题分析分析以下几条sql的索引使用情况SELECT*FROMemployeesWHEREname='LiLei';SELECT*FROMemployeesWHEREname='LiLei'ANDage=22ANDposition='manager';SELECT*FROMemployeesWHEREage=22ANDposition='manager';SELECT*FROMemployeesWHEREname='LiLei'ANDage>22ANDposition='manager';SELECT*FROMemployeesWHEREname!='LiLei';Mysql索引定义MySQL官方对索引的定义为：

索引（Index）是帮助MySQL高效获取数据的数据结构

索引的本质：

索引是数据结构，而且是实现了高级查找算法的数据结构索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作索引结构索引结构二叉树红黑树HASHBTREE数据结构教学网站：/~galles/visualization/Algorithms.html磁盘存取原理

寻道时间(速度慢，费时)

旋转时间(速度较快)

预读：长度为页的整倍数（主存和磁盘以页为单位交换数据，一页4K）Hash索引如果是等值查询，哈希索引明显有绝对优势，前提：键值唯一哈希索引没办法完成范围查询检索哈希索引也没办法利用索引完成排序，以及like‘xxx%’这样的部分模糊查询哈希索引也不支持多列联合索引的在有大量重复键值情况下，哈希索引的效率也最左前缀原则是极低的，因为存在哈希碰撞问题B-TreeB-Tree度(Degree)-节点的数据存储个数叶节点具有相同的深度叶节点的指针为空节点中的数据key从左到右递增排列B+TreeB+Tree(B-Tree变种)非叶子节点不存储data，只存储key，可以增大度叶子节点不存储指针顺序访问指针，提高区间访问的性能B+TreeB+Tree索引的性能分析一般使用磁盘I/O次数评价索引结构的优劣预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/OB+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)MyISAM索引实现MyISAM索引实现(非聚集)MyISAM索引文件和数据文件是分离的InnoDb索引实现InnoDB索引实现(聚集)数据文件本身就是索引文件表数据文件本身就是按B+Tree组织的一个索引结构文件聚集索引-叶节点包含了完整的数据记录为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？