MySql（一）索引

数据库中，最重要的概念，就是索引了吧。

数据库使用中一个普遍的场景“读写比例在10:1左右”，这个比例实际中可能更高。

Mysql的索引数据结构

引用官网5.5版本文档上的一句话：

Most MySQL indexes (PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees. Exceptions are that indexes on spatial data types use R-trees, and that MEMORY tables also support hash indexes.

常用的索引，都是基于B数的，这里的B树是个广义上的名字（包括B+Tree），特例就是地理空间索引使用了R树，基于内存的引擎使用的是Hash索引，也可以使用BTree，原文如下：

You can create indexes on spatial data types. Only MyISAM supports R-tree indexes on spatial types. Other storage engines use B-trees for indexing spatial types (except for ARCHIVE, which does not support spatial type indexing).

The MEMORY storage engine uses HASH indexes by default, but also supports BTREE indexes.

B-Tree

首先B树是一个二叉查找树，这“B”的意思，wiki上参考，很可能是作者的赞助商波音（Bayer）的首字母。

这个B树特性非常适合的数据库的存储，直接引用wiki：

• keeps keys in sorted order for sequential traversing
• uses a hierarchical index to minimize the number of disk reads
• uses partially full blocks to speed insertions and deletions
• keeps the index balanced with a recursive algorithm

keys是按照顺序排列的，这样非常利于进行索引。使用一个层次化的索引，而且出度很大，树很矮（一般高度为3），能够最小化磁盘读取次数；第三点，为了应对插入和删除，blocks中有预留的空间，MongoDB中文档与文档也有个浪费的空间。

B-Tree Index VS Hash Index

主要参考Comparison of B-Tree and Hash Indexes，不同主要是存储的结构导致的，BTree这种结构的Key值是有序的，这就导致了在范围查询、order by等操作上BTree Index是有优势的，第二个主要的区别就是，BTree可以利用最左前缀匹配特性，一个索引顶上好几个用，具体的有如下几点：

• A B-tree index can be used for column comparisons in expressions that use the =, >, >=, <, <=, or BETWEEN operators. The index also can be used for LIKE comparisons if the argument to LIKE is a constant string that does not start with a wildcard character.Hash Indexes are used only for equality comparisons that use the = or <=> operators (but are very fast).
• (Hash Index)Only whole keys can be used to search for a row. (With a B-tree index, any leftmost prefix of the key can be used to find rows.) B树有最左前缀匹配原则，一个联合索引可以顶上好几个索引，而且联合索中包含了部分value，很多查询通过索引就完成了，不会二次访问。Hash Index 没有这性质。
• (Hash Index)The optimizer cannot use a hash index to speed up ORDER BY operations. (This type of index cannot be used to search for the next entry in order.)在查询的结果需要order by的时候，可以利用相关的by 字段的索引进行快速的排序。
• (Hash Index)MySQL cannot determine approximately how many rows there are between two values (this is used by the range optimizer to decide which index to use). 对于存在多个索引的情况在，MySQL也是比较智能的，会分析下使用哪个Index比较好，而分析的一个依据是两个value之间有多少的值。

索引

参考美团的MySQL索引原理及慢查询优化，建立索引的基本原则：

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)的索引，那么只需要修改原来的索引即可

主键的要求

对于一般使用B+树的索引，对于主键有两点要求，以下说明都基于InnoDB引擎。

第一，占用空间越小越好，因为索引中会存储主键的值，所以主键占用磁盘越小，主索引总大小也就越小，占用内存也就越小。而且二级索引（辅助索引）会直接引用主索引中的值，主键越小，二级索引也就越小。InnoDB必须有主键，如果不显示指定，会生成一个6字节的整形。

第二，最好单调，虽然B+树使用不完全填充的块来加速插入和删除，一是如果非单调，那么在块内也是需要调整的，二是一些情况下，块内可能都放不下了，需要进行块级别的调整，开销就更大了。非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整。

内存使用

对于InnoDB，如果整个索引，索引文件的大小（不算叶子节点）是与主键*数目条数是一个数量级的（1/3左右），如果是百万级别的数目，索引的长度是10，那么，内存中的索引大小也就10M，10亿级别，大小是10G，现代的机器动不动就128g的内存，也是可以的。如果从索引的角度看，Mysql对于10亿级别的数据，查找性能上，简单情况，应该问题不大。

对于MongoDB，默认的索引使用的是B-Tree而不是B+Tree，具体原因目前没有找到靠谱的说法，但是从原理上推断，B树与B+树比，节点中包括了具体的文档的地址，如果不考虑IO访问速度，那么B树不用每次都访问到叶子节点才找到具体的文档的地址，查找效率比B+树要高。当然，这里有个前提假设，IO的访问速度不考虑在内，如果使这种假设近似实现呢？一是加上更大的内存，让索引整个都在内存中，二是使用随机IO更好的固态磁盘，可以看到，这两个假设都是现代计算机发展的一个趋势，这么推测，在一定的场景下，从索引上看，MonggoDB比使用B+树的数据库，性能可能更好一点。

问题

还是上面这个问题，在扩展下，在Stackoverflow上看到的一个问题：

For what specific reasons making the designer of MySQL, MongoDB, Lucene choosing different index implementation ?

• MySQL: B+Tree
• MongoDB: B-Tree
• Lucene: Skip List

TODO

参考

MySQL索引原理及慢查询优化 MySQL索引背后的数据结构及算法原理 mysql里创建‘联合索引’的意义？ B-tree