-
- OLTP与OLAP
-
不同应用中B+树索引的使用
-
联合索引
-
覆盖索引
-
INDEX HINT
-
Multi-Range Read
-
Index Condition Pushdown
-
T树索引
-
- T树概述
-
T树的查找、插入和删除操作
-
T树的旋转
-
哈希索引（索引不再是B+树，而是一个散列表）
-
- 散列表
-
InnoDB存储引擎中的散列算法
-
自适应哈希索引
根据存储介质的不同，可以将数据库分为基于磁盘的数据库系统、基于内存的数据库系统，以及混合型数据库系统。基于磁盘的数据库系统是最为常见的一种关系型数据库，比如MySQL、SQL Server。随着内存的使用不断增加，基于内存的数据库系统也变得十分流行了，而混合型数据库系统就是将上述两种数据库的有点进行了结合。
毫无疑问，基于内存的数据库系统是最快的，因为数据库不需要对磁盘进行操作，磁盘的速度要远远慢于内存的速度，因此基于磁盘的数据库系统一斑都有缓冲池，即一块内存区域，其作用是从磁盘上读取的指定大小数据——称为页或块，放入缓冲池中，当再次读取的时候，数据库会首先判断该页是否在缓冲池中，如果在的话，会直接从缓冲池中读取缓冲池中的页，如果不在则读取磁盘上的页（读取了就会放入缓冲池中）。而对于写的操作，数据库将页读入缓冲池中，然后在缓冲池中对页进行修改，修改完成的页一般被异步地写入磁盘中（异步即开启另一个线程去写，不影响当前的使用，同步是要完成当前的动作，才能开启下一个动作）。
对于缓冲池的维护一般采用LRU算法，由此可见，缓冲池的大小决定了数据库的性能，若数据库中的数据可以完全存放于缓冲池中，则可以认为这时的数据库是最优的，除了同步/异步的写磁盘的操作外，所有其他操作都可以在内存中完成。
对于MySQL数据库系统，由于其有着各种不同的存储引擎，因此其缓冲池是基于存储引擎的，也就是说每个存储引擎都有自己的缓冲池。对于MyISAM存储引擎来说，变量key_buffer_size决定了缓冲池的大小，对于InnoDB存储引擎来说，变量innodb_buffer_pool_size决定了缓冲池的大小。
现在我们来了解一下读取页（磁盘储存数据的单位）的方式
总共有2种方式，第一种是顺序读取，顺序读取是指按顺序地读取磁盘上的页，第二种是随机读取，随机读取并不是指随机去读取，而是指访问的页并不是连续的，即需要磁盘的磁头不断移动（传统的机械硬盘是由磁头、磁道、扇区、柱面组成的，读取时需要通过磁头的移动来定位数据，这个时间称为寻道时间）。这里需要注意的是，这里的顺序是指逻辑上的顺序（即获取页中的数据，数据的先后），在物理上不可能保证所有的数据都是顺序的（即页在磁盘中的分布都是按顺序来的），而为了保证顺序，数据库存储引擎一般都是根据区来管理页，例如在InnoDB存储引擎中的一个区是64( 2 6 2^6 26)个页，因此在顺序读取数据库时，可以保证这64个页是连续的，而区与区之间的页，可能连续也可能不连续（比如某个表数据需要4页的存储空间，然后这个区只剩下3页，那么是明显不够的，需要另一个区再提供一页，那么这两个区的数据就连续了）
B+树索引B+树的索引的本质就是B+树在数据库中的实现，而B+树索引在数据库中的一个特点就是高扇出性（就是结点可以放多个数据，每个数据又看作一个小结点，每个小结点的下一层又可以放左右两个结点，比如一个4-结点，那么这4-结点的子结点就有8个），例如在InnoDB存储引擎中，每个页的大小为16KB（页在B+树的体现，就是B+树的叶子结点，因为页是存储数据的，B+树只有叶结点有数据，注意这里的叶结点也是什么M-结点的，所以一个页是有多行数据的，也就是多个data，16KB也就大概16个结点），因此树的高度一般都在2~4层。
这意味着使用索引进行一次查找，顶多需要2到4次的IO操作（访问磁盘，或者访问缓存区）。
B+树索引可以分为聚集索引和辅助索引（即非聚集索引），但是这两者本身本质都与B+树结构一样，区别仅仅在于所存放的数据不同。
InnnoDB的B+树索引InnoDB的存储引擎索引组织表，也就是说数据文件本身（页和块）就是按照B+树方式存放数据的。其中，B+树的键值为主键，若在建立时没有显示地指定主键，则InnoDB存储引擎会自动创建一个6字节的列作为主键，. 如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引（跟Redis差不多，自动创建一个UUID，但不同的是这里创建的是ROWID，而且不像UUID一样是无序的！因为无序会在结点中间进行插入，那么就要进行维护，有序的话直接在尾巴后面插入即可），因此在InnoDB存储引擎中，可以将B+树索引分为聚集索引（显示地自定义主键）和辅助索引（针对没有显示生成主键，自动生成主键的情况），无论是何种索引，每个页的大小都为16KB（限定了B+树的叶子结点最多方能放多少个数据），且不能更改。
两种索引
聚集索引是根据主键创建的一棵B+树，聚集索引的叶子结点放了表中的所有记录（也就是数据），辅助索引是根据索引键（自动生成的索引值）创建的一棵B+树，与聚集索引不同的是，其叶子结点仅仅存放索引键值（仅仅存放主键值），以及该索引键值指向的主键（这里是自动生成的主键）。也就是说，如果通过辅助索引来查找数据，那么当找到辅助索引的叶子结点后，很有可能还需要根据主键值查找聚集索引来得到数据，这种查找方式又称为书签查找（因为里面除了有辅助索引的索引值和主键值外【对应为k,v】，还有一个值，存储的是聚集索引的位置，这个值称为书签），因为辅助索引不包含行目录的所有数据，这就意味着每页可以存放更多的键值，因此其高度一般都要小于聚集索引（但效率不一定高，因为找到真实的数据，需要去搜索对应的聚集索引的B+树）。
MyISAM的B+树索引MyISAM存储引擎其实更像一张堆表，所有的行数据都存放于MYD文件中，其B+树索引都是辅助索引，存放于MYI文件中。PRIMARY KEY索引（主键索引）和其他索引不同之处在于其必须是唯一的，并且不可以为NULL值，其索引页的大小默认为1KB（InnoDB是16KB），同样是不可以进行调整的（MySQL的所有引擎都不可以对索引页进行大小调整，但可以调整缓冲池大小）。此外，与InnoDB存储引擎不同的是，因为没有聚集索引，其索引结点存放的键值不是主键值（相当于没有主键，InnoDB只要定义了主键，就会生成聚集索引），而是MYD文件中的物理位置（直接映射磁盘的真实位置）。
Cardinality 什么是Cardinality?并不是所有在查询条件中出现的列都需要添加索引，对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分行时使用B+树索引才有意义，比如性别字段、地区字段、类型字段，他们可取值的范围很小，称为低选择性。
下面举个栗子
SELECt * FROM student WHERe sex = ‘M’;
这句SQL是查找学生表中的男生，sex的字段里面只有M和F，因此上述的SQL得到的结果大概是50%左右数据（假设男女比例为1：1），这时添加B+树是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即是高选择性的（比如用户表的id），那么此时使用B+树索引是最适合的，例如姓名字段，基本上在每一个应用中都不允许出现重名。
那要怎样查看索引是否是高选择性呢？这里可以通过使用SHOW INDEX语句中的Cardinality列来观察，Cardinality值是非常关键的，表示索引中唯一只记录数量的遇预估值。这里需要注意的是，Cardinality只是一个预估值，而不是一个准确值，用户也不可能得到一个准确的值。在实际应用中，Cardinality/n_rows_in_table应尽可能接近1，如果非常小，那么就要考虑是否需要重建索引了
EXPLAIN SELECt * FROM account WHERe id = 500;
这里id字段有个主键索引，这时进行查找，并且查找id=500，得到的执行计划如图所示
可以看到使用了id这个索引，符合前面提到的高选择性，只选取表中很少的行原则
B+树索引的使用 OLTP与OLAPOLTP主要执行基本的、日常的事务处理，比如在银行进行存取一笔钱，就是一个事务交易，它的特点有
-
实时性要求高
-
查询的数据量不是很大
-
交易一般是确定的，所以OLTP是对确定性的数据进行存取
-
并发性要求高，并且严格要求事务的完整性、安全性
OLAP是数据仓库系统的主要应用，典型的应用就是复杂的动态报表系统，OLAP的特点一般有
-
实时性要求不是很高，很多应用最多一天只查一次
-
数据量大，因为OLAP支持动态查询，用户要通过对很多数据的统计才能得到想要的信息
-
终点在于决策支持，所以查询一般是动态的，也就是说允许用户随时提出查询的要求
OLTP应用中，用户只要查询一小部分的数据，一般都在10条记录以下，甚至大多数情况只有1条（比如根据主键去查找用户信息，根据订单号取得订单信息，这些都是典型的OLTP应用的查询语句），在这种情况下，建立B+树索引后，对该索引的使用应该只是通过该索引获取小部分的数据，这时建立B+树索引才有意义的，否则即使建立了，优化器也可能选择不适用索引。
但对于OLAP应用，情况就比较复杂了，不过总的来说，OLAP都需要访问表中大量的数据，并根据这些数据来产生查询的结果，一般不太需要索引，但是对于复杂查询，如果需要涉及多张表之间的联接操作，这时索引的添加可能才会有意义（联接操作，减少了数据量）
联合索引联合索引是指对表上的多个列进行索引。
下面举个栗子
CREATE TABLE t(
a INT,
b INT,
PRIMARY KEY(a),
KEY idx_a_b(a,b)
)ENGINE=Innodb,charset=utf8;
上面的SQL语句定义了a为主键索引，然后又定义了(a,b)为联合索引
下面我们来分析一下联合索引有什么用
按上面的SQL，生成的索引如下面所示，对应分别为(a,b)
我们可以看到与前面的聚集索引或者非聚集索引的B+树没什么区别，除了联合索引的键值数量不是1，而是大于或者等于2。
因此，对于WHERe a = “xxx” and b = “xxx”；的SELECt语句显然是可以使用的，对于单个列的a列查询，即WHERe a = "xxx"的SELECT语句也是可以使用的，但对于b列的查询，就不可以使用了，因为我们可以看到叶子节点上的b值，并不是按顺序进行排列的，因此对b列的查询不可以使用联合索引
联合索引的另一个好处就是可以对第二个键值进行排序，下面举个栗子
CREATE TABLE buy_log(
userid INT UNSIGNED NOT NULL,
buy_date DATE
)ENGINE=INNODB;
INSERT INTO buy_log VALUES(1,‘2009-01-01’);
INSERT INTO buy_log VALUES(2,‘2009-01-01’);
INSERT INTO buy_log VALUES(3,‘2009-01-01’);
INSERT INTO buy_log VALUES(1,‘2009-02-01’);
INSERT INTO buy_log VALUES(3,‘2009-02-01’);
INSERT INTO buy_log VALUES(1,‘2009-03-01’);
INSERT INTO buy_log VALUES(1,‘2009-04-01’);
ALTER TABLE buy_log ADD KEY(userid);
ALTER TABLE buy_log ADD KEY(userid,buy_date);
然后执行下列的语句
EXPLAIN SELECT * FROM buy_log WHERe userid = 2;
优化器选择了使用单个列的聚集索引，因为这个索引的叶子结只有1个键值，也就是这个结点能存放更多的键值（一页有16KB，然后一个叶子结点就是一页）
可以看到选择器选择了userid_2这个索引，也就是联接索引，因为在这个联合索引中，buy_date是已经排序好了，如果使用这个索引进行取出数据，就无需再对buy_date做一次额外的排序操作（可以看到在Extra列上，只有使用了index scan和index，并没有using filesort）。
强制使用单一列来索引的话
EXPLAIN SELECt * FROM buy_log FORCE INDEX(userid) WHERe userid = 2 ORDER BY buy_date DESC LIMIT 3;
可以看到Extra里拥有using filesort，即表明了需要额外的一次排序才能完成查询，而这次排序明显是对buy_date进行排序。
覆盖索引InnoDB存储引擎支持覆盖索引，或称为索引覆盖，即从辅助索引中就可以得到查询记录，而不需要查询聚集索引中的记录（一般辅助索引里面存放索引键值，然后还要根据索引键值去查找聚集索引），即叶子结点已经包含了想要的数据，不需要再去聚集索引中找完整的数据，引用覆盖索引的好处是辅助索引不包含整行记录的所有信息，故其大小会远小于聚集索引，因此可以减少IO操作。
对于InnoDB存储引擎的辅助索引而言，叶子结点是包含主键信息的，所以页中存储的内容大概是(primary key 1,primary key 2…,key 1,key 2)这样的数据，所以下列的SQL语句都可以直接查询这些数值出来，而不需要额外去找聚集索引
SELECt key2 FROM table WHERe key 1 = xxx;
SELECt primary key2,key2 FROM table WHERe key 1 = xxx;
SELECt primary key1,key2 FROM table WHERe key1 = xxx;
SELECt primary key1,primary key2,key1,key2 FROM table WHERe key1 = xxx;
覆盖索引的另一个好处就是，辅助索引会小于聚集索引（由于每条行数据的列不全），可以减少IO操作。
用上面的bug_log表为例
EXPLAIN SELECt COUNT(*) FROM buy_log;
Using index其实就是覆盖索引操作
此外，一般来说对于诸如(a,b)这样的联合索引，一般不可以选择b列作为查询条件，但如果是对于统计操作，会选择覆盖索引来进行优化。
INDEX HINTMySQL数据库支持INDEX HINT（索引提示），显示地告诉优化器使用哪个索引，下面这两种情况可能需要使用到INDEX HINT。
-
MySQL数据库的优化器错误地选择了某个索引（这种情况比较少见，优化器在绝大部分情况下工作都是正确的），导致SQL语句运行得很慢。这时候就需要强制使用正确的索引
-
某SQL语句可以选择的索引非常多，这时优化器选择执行计划时间的开销可能会比较大，当大于执行SQL本身的时候，就需要强制使用某个索引了。
如何使用INDEX HINT
USE INDEX(列)
下面举个栗子
首先我们来介绍一下mySQL的几种key
1、key 是数据库的物理结构，它包含两层意义和作用，
一是约束（偏重于约束和规范数据库的结构完整性），
二是索引（辅助查询用的）。
2、primary key 有两个作用，
一是约束作用（constraint），用来规范一个存储主键和唯一性，
二是在此key上建立了一个主键索引（在InnoDB上就是聚集索引）；
还有一点要注意的是primary key拥有自动定义的unique约束，也就是唯一
3、unique key 也有两个作用，
一是约束作用（constraint），规范数据的唯一性，
二是在这个key上建立了一个唯一索引；
再简单介绍一下什么是Using Where 和 Using Index
Using Where
usingwhere则表示需要查询磁盘里存储的数据，速度会慢很多，即就是一般的辅助索引，从辅助索引的B+树中找到主键，然后去聚集索引中根据主键去找数据。
Using Index
usingindex是覆盖索引，说明你的查询语句可以只通过查询索引里的信息就能得到结果。
注意
UNIQUE 和 PRIMARY KEY 约束均为列或列集合提供了唯一性的保证。
但一个表可以有多个unique key但只可以有一个primary key
回到上面的INDEX HINT
建一个表，并插入一些数据
CREATE TABLE w(
a INT,
b INT,
KEY(a),
KEY(b)
)ENGINE=INNODB;
INSERT INTO w SELECt 1,1;
INSERT INTO w SELECT 1,2;
INSERT INTO w SELECT 2,3;
INSERT INTO w SELECT 2,4;
INSERT INTO w SELECT 1,2;
//下面看一下语句执行情况
EXPLAIN SELECT * FROM w WHERe a = 1 AND b = 2;
可以看到Extra那里，在possible_keys那里显示了可以使用的索引为(a,b)，而实际使用的索引为key，为(b,a)，也就证明了，使用了a,b这两个索引来完成查询的，然后Extra那里有Using intersect（b,a），表示根据两个索引得到的结果然后进行交集运行（就是用a的索引，找到a=1的数据，然后用b的索引，找到b=2的数据，然后这两部分数据进行一个求交集得出a = 1 AND b = 2）
下面，使用USE INDEX的INDEX HINT来使用a这个索引
EXPLAIN SELECt * FROM w USE INDEX(a) WHERe a = 1 AND b = 2;
这里，我们可以看到优化器的确只用了索引a去做，但是执行那里依然有Using Where，表示采用了表扫的方式(依然要进行IO操作去磁盘中找数据)，并没有采用Using Index(因为，这里规定使用了INDEX(a)，所以优化器应该也会使用Using INDEX的)，因此，USE INDEX只是告诉优化器可以选择该索引，而实际上优化器还是会根据自己的判断进行选择的。
下面，强制使用FROCE INDEX，看下执行情况
EXPLAIN SELECt * FROM w FORCE INDEX(a) WHERe a = 1 AND b = 2;
可以看到，与USE INDEX也是一样的，证明，即使使用FORCE，优化器也会根据自己的判断进行选择。
总结
因此，如果用户确定指定某个索引来完成查询，那么最可靠的还是使用FORCE INDEX，而不是USE INDEX。
Multi-Range ReadMySQL数据库5.6版本开始就开始支持Multi-Range Read（缩写为MRR）优化，MRR优化的目的就是减少磁盘的随机访问，并且将随机访问转化为较为有顺序的数据访问，这样的话就可以减少IO操作，可为IO-bound类型的SQL查询语句带来性能的极大提升，MRR优化试用于Range、ref和eq_ref类型的查询。
MRR优化有以下几个好处
-
使得数据访问变得较为有顺序，在查询辅助索引时，将查到的数据结果根据主键大小进行排序（查到的结果并不只一条，但主键值一定不一样），并按照主键排列的顺序进行书签查找（即使用辅助索引结点里面存储的书签值，因为主键一般是有序自增的字段，存的时候也是按顺序存的，所以按顺序去读取，可以减少读取的页数）
-
减少缓冲池中页被替换的次数（因为减少了对页的读取，所以也会减少缓冲池中页的替换）
-
批量处理对键值的查询操作。
对于InnoDB和MyISAM存储引擎的范围查询和联接查询，MRR的工作方式如下
-
首先将查询得到的辅助索引键值存放在一个缓存中，此时是根据辅助索引的键值来排序的（并不是主键）
-
将缓存中的键根据ROWID进行再一次排序（此时才是根据主键进行排序）
-
根据ROWID的排序顺序来访问实际的数据文件
假如InnoDB存储引擎和MyISAM存储引擎的缓冲池不是很大，不够用，也就是缓冲池出现了不能存放一张表的现象（一张表有多页），那么此时频繁的离散读取操作会导致将缓存中的页替换出缓冲池，然后又不断地读入进缓冲池（比如要找的这条数据在A页，那么就将A页读取进缓冲池，另一条数据却在B页，那么又要将B页读取进缓冲池，此时另一条数据在C页，缓冲池已经满了，要从A、B中选出一个页出来被C页替换掉，如果下一条数据还是在A页，那么又要如此找一个页被A页替换掉），若按照主键去读取的话，可以将重复行为降到最低，因为页中存储的数据都是按主键顺序来排的，即如果按顺序排列的话，第一条数据和后面几条数据很可能都在同一页。
总的来说，就是回表查询的速度更快了。
此外，MRR还可以将某些范围查询拆分为键值对，以此来完成批量的数据查询的数据查询。这样做的好处是可以在拆分过程中，直接过滤一些不符合查询条件的数据
比如下面的这条SQL
SELECt * FROM t WHERe key_part1 >= 1000 AND key_part1 < 2000 AND key_part2 = 10000;
