Mysql 索引概念回顾

一、什么是索引

        在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。
        能实现快速定位数据的一种存储结构，其设计思想是以空间换时间

二、索引的分类

按 [ 数据结构 ] 分类：B+tree索引、Hash索引、Full-text索引。

按 [ 物理存储 ] 分类：索引 (主键索引) 、二级索引(辅助索引)。

按 [ 字段特性 ] 分类：主键索引、唯一索引、普通索引、前缀索引。

按 [ 字段个数 ] 分类：单列索引、联合索引。  

三、MySQL如何实现的索引机制

在MySQL 中有不同的存储引擎比如像 InnoDB MyISAM Memory 等等每一种存储引擎在其内部实现索引机制的原理也有所不同。

在 MySQL5.5 之后默认的就是 InnoDB，并且是目前使用最广泛的MySQL数据引擎，以 InnoDB为例。

1. 如果说在表中有100条数据，而要找出所需要的数据，有哪些办法?

• （不推荐）按照一种顺序的方式一条一条往下去搜索，直到匹配到需要的数据，这是一种方案在时间复杂度上是0(N)，虽说效率差但也能用。
• （不推荐）二分查找法也是一种常用的比较高效的查询算法，它的搜索效率为 0(log(N)),虽说查找效率是比顺序查找高了不少，但是它有两个前提条件，必须用顺序存储结构比如数组，第二个是必须按照关键字进行有序排序(从小到大)。
• （不推荐）哈希查找，哈希查找的特性是能够做到直接定址，其效率无限接近于 0(1)，取决于冲突的数量。但是散列表数据是无序存储的，排序要自己做，第二个是散列表还要扩容耗时长，遇到散列冲突性能不稳定。
• （推荐）B树/B+树查找的复杂度是 0(log2(N))，那么这也是InnoDB 采用的数据结构，在查找效率上的非常高的。

 B+Tree

平衡二叉树

B+ tree