Mysql 索引

问题：为什么mysql 索引使用的是b+tree 而不是b tree常问

 

数据库最常见的慢查询优化方式是什么？ --索引

为什么加索引能优化慢查询？--

你知道哪些数据结构可以提高查询速度？--

有多个数据结构都能优化查询速度，为什么mysql使用的是b+tree？--

 

局部性原理

    空间局部性：程序访问磁盘只会访问磁盘中的某一部分

    时间局部性：最近被访问的数据，很快又被访问的可能性很大

磁盘预读

 

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

? 索引存储在文件系统中

? 索引的文件存储形式与存储引擎有关

? 索引文件的结构

– hash

– 二叉树

– B树 – B+树

 

存储引擎：InnoDB,MyiSAM

    根据存储文件和存储位置的不通可分为两种索引

聚簇索引：数据和文件放在一起 innodb

            .frm：存放表结构

            .idb：存放数据文件和索引文件

    注：mysql的innodb存储引擎默认情况下会把所有的数据文件放到表空间，不会为没一个单独的表保存一份数据文件，如果需要将每一个表单独使用文件保存，设置如下属性：set global innodb_file_per_table=on

 

非聚簇所以:数据和索引单独一个文件：MyISAM

            .frm:存放表结构

            .MYI:存放索引数据

            .MYD:存放数据

 

哈希表可以完成索引的存储，每次计算完哈希值，计算好下标位置，去相应的位置找，

哈希表适合：

    等值查询

哈希表会把数据加载到内存，比较消耗内存空间，不是很合适

 

数据结构：

二叉树：

    右节点都必须大于根节点，假设根节点为0，先后插入123456789的数据，会一直在树的右侧加，那么会导致树变成了一个链状结构，造成树的深度过深造成io次数变多，影响读取的效率，因为链状结构的查询速度是比较慢的，深度越深，就代表链越长所以查询越慢

平衡树：

    AVL树（二叉平衡树），任意子节点的高度差要小于等于1，假设根节点还是0如果插入123456789的数据，当插入2的时候因为右侧有两个节点而左侧没有节点，AVL树会做个一个自旋的操作，会把1作为根节点 0作为左侧子节点 2作为右侧子节点，因为这个操作会导致insert的效率变慢

红黑树：

    红黑树是在AVL二叉平衡树的基础上进行了优化，在查询和添加中作了个平衡，在原有高度差小于等于1修改为最大节点最大是最小节点的二倍，即最小节数点有8个节点，那么最大节点数是16，假设要查询节点16上的数据，这样也会造成io次数多，影响读取效率

多叉树

    B树：

        每个节点可以有很多个子节点，具体如图

 

        这里会发现data数据会和键值放在一起，这会导致如果data数据较大，那么磁盘中存储的key值即键值           会 变少，影响效率。

B+树：

    在B树的基础上做出优化

非叶子节点存储key值，叶子节点存储key值和data数据，这样的话如图的上面两层其实只存放一个指针和一个键值所占空间是很小的，以一个磁盘块为4kb来看，一个数据大小为10kb，一个磁盘块能存放400条，第二层也是400条，假设第三曾就是如图一般只能存放4个数据那么可存储的数据就有400*400*4=64万条的数据，而且他只有3层结构，查询速度快