数据库索引总结

一，索引的种类

一，从数据结构角度

B+树索引(O(log(n)))：n是记录总树，底数是树的分叉数，结果就是树的层次数,关于B+树索引，可以参考MySQL索引背后的数据结构及算法原理
- B+树是一颗平衡树，如果我们对这颗树增删改的话，那肯定会破坏它的原有结构。
- 要维持平衡树，就必须做额外的工作。正因为这些额外的工作开销，导致索引会降低增删改的速度
hash索引：哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

hash索引的缺点：
- 哈希索引也没办法利用索引完成排序
- 不支持最左匹配原则
- 在有大量重复键值情况下，哈希索引的效率也是极低的—->哈希碰撞问题。
- 不支持范围查询，仅仅能满足”=”,”IN”和”<=>”查询，不能使用范围查询
- 其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引
- 只有Memory存储引擎显示支持hash索引
FULLTEXT索引（现在MyISAM和InnoDB引擎都支持了）
R-Tree索引（用于对GIS数据类型创建SPATIAL索引）

二，从物理存储角度

聚集索引(clustered index)就是以主键创建的索引
非聚集索引(non-clustered index)就是以非主键创建的索引
- 区别：
  - 聚集索引在叶子节点存储的是表中的数据
  - 非聚集索引在叶子节点存储的是主键和索引列
  - 使用非聚集索引查询出数据时，拿到叶子上的主键再去查到想要查找的数据。(拿到主键再查找这个过程叫做回表)

三，从逻辑角度

主键索引：主键索引是一种特殊的唯一索引，不允许有空值
普通索引或者单列索引
多列索引（复合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合；
- 我们前面知道了，如果不是聚集索引，叶子节点存储的是主键+列值
- 最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢
- 覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！
- 比如说：
  - 现在我创建了索引(username,age)，在查询数据的时候：select username , age from user where username = 'Java3y' and age = 20。
  - 很明显地知道，我们上边的查询是走索引的，并且，要查询出的列在叶子节点都存在！所以，就不用回表了~
  - 所以，能使用覆盖索引就尽量使用吧~
唯一索引或者非唯一索引
空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。
MYSQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类型的语法创建空间索引。创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MYISAM的表中创建

索引最左匹配原则：

索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即联合索引。
如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。
因此，列的排列顺序决定了可命中索引的列数。

例子：
如有索引(a, b, c, d)，查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。(很简单：索引命中只能是相等的情况，不能是范围匹配)

索引总结

索引在数据库中是一个非常重要的知识点！上面谈的其实就是索引最基本的东西，要创建出好的索引要顾及到很多的方面：

1，最左前缀匹配原则。这是非常重要、非常重要、非常重要（重要的事情说三遍）的原则，MySQL会一直向右匹配直到遇到范围查询（>,<,BETWEEN,LIKE）就停止匹配。
3，尽量选择区分度高的列作为索引，区分度的公式是 COUNT(DISTINCT col) / COUNT(*)。表示字段不重复的比率，比率越大我们扫描的记录数就越少。
4，索引列不能参与计算，尽量保持列“干净”。比如，FROM_UNIXTIME(create_time) = '2016-06-06' 就不能使用索引，原因很简单，B+树中存储的都是数据表中的字段值，但是进行检索时，需要把所有元素都应用函数才能比较，显然这样的代价太大。所以语句要写成： create_time = UNIX_TIMESTAMP('2016-06-06')。
5，尽可能的扩展索引，不要新建立索引。比如表中已经有了a的索引，现在要加（a,b）的索引，那么只需要修改原来的索引即可。
6，单个多列组合索引和多个单列索引的检索查询效果不同，因为在执行SQL时，MySQL只能使用一个索引，会从多个单列索引中选择一个限制最为严格的索引。

参考文档：

数据库两大神器【索引和锁】

MySQL的索引

深入浅出的理解数据库索引

阿里巴巴Java开发手册

二，数据库引擎

一，Innodb

InnoDB是事务型数据库首选引擎，支持事务安全表(ACID),支持行锁定和外键，InnoDB是默认的MySQL引擎。InnoDB主要特性有：

InnoDB给MySQL提供了具有提交、回滚和崩溃恢复能力的事物安全（ACID兼容）存储引擎。InnoDB锁定在行级并且也在SELECT语句中提供一个类似Oracle的非锁定读。这些功能增加了多用户部署和性能。在SQL查询中，可以自由地将InnoDB类型的表和其他MySQL的表类型混合起来，甚至在同一个查询中也可以混合
InnoDB是为处理巨大数据量的最大性能设计。它的CPU效率可能是任何其他基于磁盘的关系型数据库引擎锁不能匹敌的
InnoDB支持外键完整性约束，存储表中的数据时，每张表的存储都按主键顺序存放，如果没有显示在表定义时指定主键，InnoDB会为每一行生成一个6字节的ROWID，并以此作为主键
InnoDB被用在众多需要高性能的大型数据库站点上

二，MyIASM

MyISAM基于ISAM存储引擎，并对其进行扩展。它是在Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM拥有较高的插入、查询速度，但不支持事物。MyISAM主要特性有：

大文件（达到63位文件长度）在支持大文件的文件系统和操作系统上被支持
当把删除和更新及插入操作混合使用的时候，动态尺寸的行产生更少碎片。这要通过合并相邻被删除的块，以及若下一个块被删除，就扩展到下一块自动完成
每个MyISAM表最大索引数是64，这可以通过重新编译来改变。每个索引最大的列数是16
最大的键长度是1000字节，这也可以通过编译来改变，对于键长度超过250字节的情况，一个超过1024字节的键将被用上
BLOB和TEXT列可以被索引
NULL被允许在索引的列中，这个值占每个键的0~1个字节
所有数字键值以高字节优先被存储以允许一个更高的索引压缩
每个MyISAM类型的表都有一个AUTO_INCREMENT的内部列，当INSERT和UPDATE操作的时候该列被更新，同时AUTO_INCREMENT列将被刷新。所以说，MyISAM类型表的AUTO_INCREMENT列更新比InnoDB类型的AUTO_INCREMENT更快
可以把数据文件和索引文件放在不同目录
每个字符列可以有不同的字符集
有VARCHAR的表可以固定或动态记录长度
VARCHAR和CHAR列可以多达64KB

使用MyISAM引擎创建数据库，将产生3个文件。文件的名字以表名字开始，扩展名之处文件类型：frm文件存储表定义、数据文件的扩展名为.MYD（MYData）、索引文件的扩展名时.MYI（MYIndex）

三，MEMORY

MEMORY表的每个表可以有多达32个索引，每个索引16列，以及500字节的最大键长度
MEMORY存储引擎执行HASH和BTREE缩影
可以在一个MEMORY表中有非唯一键值
MEMORY表使用一个固定的记录长度格式
MEMORY不支持BLOB或TEXT列
MEMORY支持AUTO_INCREMENT列和对可包含NULL值的列的索引
MEMORY表在所由客户端之间共享（就像其他任何非TEMPORARY表）
MEMORY表内存被存储在内存中，内存是MEMORY表和服务器在查询处理时的空闲中，创建的内部表共享
当不再需要MEMORY表的内容时，要释放被MEMORY表使用的内存，应该执行DELETE FROM或TRUNCATE TABLE，或者删除整个表（使用DROP TABLE）

四，Achive

功能	MYISAM	Memory	InnoDB	Achive
存储限制	256TB	RAM	64TB	None
支持事务	no	no	yes	no
支持全文索引	yes	no	no	no
支持数索引	yes	yes	yes	no
支持哈希索引	no	yes	no	no
支持数据缓存	no	N/A	yes	no
支持外键	no	no	yes	no

黄杰|博客