MySQL系列（一）：基础知识大总结

MySQL系列（二）：MySQL事务

MySQL系列（三）：索引

什么是索引

如果没有索引，扫描的记录数大于有索引的记录数

索引存放索引列的值（比如id为索引列，那么存放索引列的值），和该索引值对应的行在内存中的地址（或者直接存储该行的数据）

SELECT * FROM user WHERE username= ‘jiajun‘ ,username建立索引，如果索引采用的数据结构是hash表，那么这个时候，通过计算jiajun的hash值，O（1）复杂度就可以找到该记录的位置

hash索引

在等值查找下，此时无hash冲突，这种情况下，效率是很高的

但是在范围查找下，由于hash不是有序的，那么范围查找下，hash表的优势并不能发挥出来。

在hash冲突下，查找效率会降下来

磁盘读取

磁盘读取步骤：定柱面，定磁道，定磁块

磁盘时间主要消耗在定位柱面，那么如果要提高速度，在数据量一样的情况下，将尽量多的数据放在磁盘块上，那么这样可以减少磁头定位柱面移动的次数，减少IO的次数。

二叉查找树

左子树所有的节点的值小于他的根节点的值

右子树所有的节点的值大于他的根节点的值

任意节点的左子树和右子树都是二叉查找树

没有键值相等的节点

分析

二叉查找树的查找的复杂度到了lgn

但是有没有办法减少IO的次数，也就是能不能降低树的高度

B-树

（m阶树 m/2<=k<=m）

根节点至少两个子节点

所有叶子节点都在同一层

中间节点包含k-1个元素和k个孩子

节点中的元素从小到大排列

每个节点即包含索引列的值，和该数据记录（或该数据记录的值）

相对于二叉查找树，B树变得矮胖，因为每个节点存放的元素更多，所以相同元素情况下，降低了树的高度，那么就可以减少IO的次数

每个节点存放了数据（该行记录的值或者该行记录在内存的地址），所以不同的查询性能是不一样的。

B+树

在B-树的基础上

除了叶子结点，其他节点不包含记录（数据库中的行）的位置

叶子节点包含了所有的索引值，并且从小到大排列，以及记录（数据库中行）的位置

如果节点的大小一样，那么如果我们除了叶节点之外，其他节点不包含数据，那么就可以放更多的元素（索引值），这样的话这棵树就变的更加矮胖，那么IO的次数可以进一步减少

因为叶节点的元素是顺序排列，而且叶节点间形成链表，那么有序查找时提高范围查询的效率

相对于B树，由于所有的数据是存放在叶节点，那么意味着每次查找都必须到从根查找到叶节点，那么这就意味着查询性能平均。

总结

索引是一种数据，可以避免了全表查询，可以类比目录和书。

索引需要一种数据结构来存储

利用散列表（hash）的方式查询复杂度可以到O（1），但是再范围查询时，hash起不了提高性能的作用

IO操作是耗时，为了提高查询性能，可以减少IO的次数

对于树的存储结构来说，为了提高性能，减少IO的次数，可以低树的高度

读取一个节点一次IO，在数据量一样的情况下，如果每个节点的能存放更多元素，那么就可以降低树的高度。

B树降低了树的高度，而在节点大小一样的情况下，因为B树的节点存放了元素有又存放了数据，而B+树将数据全部存放在叶节点，那么这样的话，每个节点可以存放更多的元素，那么就可以再一次降低树的高度

B+树的查询性能更加稳定，并且更有利于范围查找

如果是聚集索引（InnoDB引擎），那么节点存放的该记录的数据，数据文件本身就是索引文件

如果是非聚集索引（MyISAM引擎），那么节点存放的是该行记录的地址。索引文件和数据文件是分离

索引的种类

普通索引，允许出现相同的内容

唯一索引，索引值唯一，允许空值

主键索引，创建主键的时候自动创建主键索引，唯一并且不能为空

组合索引，多列组合索引

索引的使用

ALTER TABLE table_name ADD INDEX index_name (column_list) 增加普通索引

ALTER TABLE table_name ADD UNIQUE (column_list) 增加唯一索引

ALTER TABLE table_name ADD PRIMARY KEY (column_list) 增加主键索引

索引优缺点

毫无疑问，在使用正确的情况下，索引能提高查询速度

索引也能提高分组和排序的速度

由于修改删除添加时，要调维护索引文件，对树进行调整，所以性能降低了

索引文件也是需要占用空间的

mysql 索引