Mysql索引详解

索引与存储引擎

想一下我们查字典的时候是不是要用偏旁部首笔画之类的去查我们想要的东西？查字典的案例就相当于使用索引。

现在我们可以将数据库分为两类，一种是OLAP，一种是OLTP。对于OLAP来说，数据主要是一些历史数据，用来做数据分析与决策的，不要求实时性，hive就是其中之一。hive建索引的三要素就是(关键值，文件名，偏移量)。

对于OLTP来说，主要是处理事务的，要求实时性较高，我们就需要更快的查询方式，也就是一个更好的数据结构。mysql使用的是B+树。

mysql还有一种数据结构叫哈希，哈希用于memory这个存储引擎。存储引擎就是数据文件在物理磁盘的组织形式。myisam和innodb(默认)使用的B+树，而memory使用的是hash索引。

那么innodb能使用hash吗？可以！但是是由mysql自适应调整，用户无法干预。
如下图是使用innodb存储引擎组织的数据文件。.frm文件存储的是表的结构，而.ibd文件存储的是真实地数据和索引。

我们在来看看myisam存储引擎的组织形式。
.frm依然是表的结构，.MYD是真实数据，.MYI是索引。

磁盘预读

我们都知道内存的读写速度与磁盘的读写速度根本不是一个量级，于是我们利用局部性原理，即使我仅仅需要从磁盘读取一个字符a，我也会将一个页的数据加载到内存。

Mysql数据结构的选择(为什么要选择B+)

先来看看hash的缺点。

那么当存储引擎为memory时，以上缺点均可忽略，因为是在内存，不管是等值查询还是范围查询，都不在乎，因为内存很快！！！
再来看看二叉树与红黑树。innodb引擎每次从磁盘取16k的页，每个树的节点就放一个值，这样会放很多节点，导致树的深度加深。

提升IO效率的两个方法
1.减少IO的次数

2.减少IO的大小

B树

我们可以看到B树在每一个磁盘块里都存放了某表里每一行的记录data，节点里面的数值是对表里的某一列（如id）建的索引列。假设么一个磁盘块(一页)有16KB，一行记录有1kb，那么每一个磁盘块可以存16行记录，然后三层的b树能存16x16x16=4096行记录(这里仅仅粗略的计算一下)

B+树

我们可以看到B+树每一个关键字出现了两次。然后只有叶子节点挂了每行的记录。假设一块还是16KB，然后关键字占10个字节，16KB/10个字节=1600个关键字，那么前两层有1600x1600的关键字，然后最后一层存data时，每一行记录为1kb，每一块存16行记录，然后1600x1600x16=40960000行记录(粗略估算)，所以三层的B+树能存的记录数是B树的10000倍。

未完待续。。。