mysql索引

• 索引简介

索引是什么

索引(Index)是帮助MySQL高效获取数据的数据结构，所以索引是一种数据结构。

为什么会有索引

假如我们现在执行一个SQL，SELECT * FROM my_table WHERE col = '77'，最基本的查询算法当然是顺序查找遍历整个表“my_table”，然后逐行匹配“col”的值是否是“77”，假如现在表里面有几千万条数据，那么就需要匹配几千万次，这样的做法显然效率很低。所以出现了加快查找的数据结构，比如二叉树查找和二分查找等，但是每一种特定的查找方法都有特定的适用环境,比如二分查找只能适用于有顺序的数组；二叉树查找只能适用于二叉树。而在数据库之中,在表数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式指向表数据（我们在这些数据结构上找到某个key，就可以找到对应的表数据了），这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

比如：

索引

图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

• 索引的类型

1. 结构

B树

B树

A.相同的域,即每个节点的大小都是相同的
B.d是B树的度,所谓度,就是

2. B树怎么查找数据
   首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：

BTree_Search(node, key) {
    if(node == null) return null;    
    foreach(node.key)    {
        if(node.key[i] == key) 
               return node.data[i];
        if(node.key[i] > key) 
                return BTree_Search(point[i]->node);    
     }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

3. B树的简历
   由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

B+树

1. 结构

   
   B+树
   

   和B树的区别是B+数的数据都在叶子节点上面，而B数的数据可以在节点上面。

2. 带有顺序访问指针的B+

   
   B+树
   

   这个优化的目的是为了提高区间访问的性能，例如上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

3. 选择 B/B+ 而不是二叉树的原理
   A.索引本身存在磁盘之中,索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
   B.数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
   C.红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

4. MyISAM引擎中的实现

   
   MyISAM索引的实现
   

   MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

5. InnoDB引擎中的实现
   InnoDB引擎也是采用B+树做索引,只是实现方式和MyISAM实现完全不一样.
   第一个重大区别是InnoDB的数据文件本身就是索引文件。而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引（primary key）。

   
   InnoDB的B+树主索引

第二个不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

InnoDB的B+树辅助索引

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

6. 如何选用合适的引擎
   了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

哈希索引

1. 是什么？
   哈希索引（hash index)基于哈希表实现，只有精确匹配索引所有列的査询才有效。对 于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code),哈希码是 一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希 码存储在索引中，同时在哈希表中保存指向每个数据行的指针。去AAAA啊
   My SQL中，只有Memory引擎显式支持哈希索引。
   如果多个列的哈希值相同， 索引会以链表的方式存放多个记录指针到同一个哈希条目中。
   2.为什么?
   因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引査找的速度非常快。
2. 创建一张使用hash索引的表

CREATE TABLE `hash_test` (
  `id` int(11) NOT NULL COMMENT '主键ID',
  `age` int(11) DEFAULT NULL COMMENT '业务模块ID',
  PRIMARY KEY (`id`),
  KEY `hash_test_age` (`age`) USING HASH
) ENGINE=MEMORY DEFAULT CHARSET=utf8 COMMENT='hash测试表';

4. 假设执行 mysql> SELECT lname FROM testhash WHERE fname='Peter';
   查询顺序：
   A.先计算peter的hash值。
   B.以此hash值，在hash表中查找对应的值，查到值为指向第三行的指针
   C.然后检查该行，看看fname是否等于peter，如果是就取出该行的数据。
   5.缺陷
   A.只支持单个查找，即“ = ”，“ in” ，不支持多个查找，范围查找。
   B.因为不支持范围查找，只能查单个，所以也就不能排序。
   6.添加hash索引: create index 索引名 using hash on 表名(列名);

• 复合索引

1. 组合索引是什么
   select * from table where column1 = 1 and column2 = 2 and column3 = 3
   假如我们要对以上的table建立索引，我们除了可以建立key(colum1),key(colum2),key(colum3)三个索引，还可以建立key(colum1,colum2,colum3)这个复合索引，普通索引是对单个字段建立的索引，复合索引是对多个字段建立的索引。

2. 组合索引的结构
   网上对复合索引的数据结构的资料甚少，我推测复合索引的结构应该如下：

   
   复合索引数据结构
   

   复合索引先按最左的第一个索引列建立B+树，在B+树的叶子节点中，下面的索引就有点像电话簿了，mysql会对第二列索引对叶子进行排序，再按第三列索引对叶子进行排序，以此类推...

3. 为什么要用复合索引
   mysql的每次查询只会搜索一个搜索，即如果我们对上面的表table建立了三个单索引，我们执行了上面的SQL以后，实际上mysql只会从这三个索引中选择最合适的一个索引来执行，而不是三个索引都会去搜。所以建立一个复合索引能有效的提高查询的性能。

4. 组合索引的特点
   根据复合索引的数据结构， Mysql从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效。

• 索引的原则

原则

1. 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式
3. 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录
4. 索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
5. 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可

性别为什么不适合当索引？

select * from user where sex = 0
假如现有user表有1百w条记录，sex中 0代表男， 1代表女，男女比例相等，即50w个男，50w个女。
我们通过计算区分度f = count(distinct col)/count(*) 得到 f = 2/1000000,接近于0，可见区分度相当的小；如果没加sex做索引，要找出所有男生的记录，那么mysql要遍历100w条记录，再把所有符合条件的数据找出来；
如果加了索引的话，mysql首先从辅助索引找出这50w条记录的id，然后再遍历50w次，从主索引中找出符合条件的记录；如此看来，其实加了索引其实遍历的次数没有减少多少，而且在实际中，要从辅助索引中查找相关记录，首先要把辅助索引从硬盘中加载到内存中去，对于这种IO操作，实际上消耗的时间也是相当大的，所以给sex加了索引不一定能提升速度。