Mysql索引数据结构详解（1）

索引是帮助Mysql高效获取数据的排好序的数据结构

常见的存储数据结构：

   二叉树不适合单边增长的数据

   红黑树会自动平衡父节点两边的节点数

   Mysql底层用的是B+树

   非叶子节点不存储data（data在Mysql中有可能是查询目标行的所有数据），

只存储索引（冗余),可以存放更多索引，减少io次数。

   叶子节点包含所有索引字段

   叶子节点用指针连接，提高区间访问的性能。

    B+树一个节点16kb，存储一个索引需要14字节 ，故一个节点可存储1170个索引，加入子节点的存储的data加上索引的大小为1kb那么一个h为n的树科存储的数据量为1170的n次方*16，只需要高为3的树既可以存储千万级的数据量，这也是为什么mysql使用B+树作为底层数据结构实现。

在mysql中的B+树实现，在子节点子之间添加了双向指针，相当于一个双向链表，这样在进行范围查询的时候查询目标值只需要沿着指针想目标方向遍历就可以获得所有所需数据，效率极高

hash表结构，通过hash散列算法实现，当传入一个key，通过进行hash计算获得的值，可以直接定位到指向目标的指针，并且hash结构的查询速度和数据量并非是成正比，即便是极大的数据量，hash表也可以以较快的速度获取结果，但是缺点是不支持模糊查询、范围查询这类查询方式，所以mysql百分之99的表使用B+树结构

关于mysql引擎，并非是所有mysql表都是innodb，mysql中每个表都可以单独设置数据库引擎的。比较常见的就是innodb和Myisam了

    .frm存储表结构

    .ibd存储索引字段和所有数据行

    表数据文件本身就是按B+Tree组织的一个索引结构文件

    聚集索引-叶节点包含了完整的数据记录

    为什么innodb表必须有主键，并且推荐使用整型的自增主键？

    答:由于innodb表数据本身就是B+组织的，所以如果不使用主键，也就没有索引，表结构无法建立，如果你不去指定主键，那么myql会隐性的建立一个rowid的字段作为主键。

    因为在mysql在建立B+树的时候牵涉到大量的大小比较，如果使用UUID这种字符串类型作为主键创建索引，明显比使用整型主键作为索引要慢的多，在之后的查询中也会慢很多，并且UUID占据的存储空间也会很大。因为每个叶子节点的大小是固定，使用的主键是非递增的，当插入一个处于中间的数值是会导致已经满了的节点需要再次分裂，b+树有可能需要再次进行平衡，会占用很多时间，而使用递增主键，那么就只需要不断的在末尾子节点后面增加节点即可，减去了很多的分裂平衡的过程以及比较大小找寻插入点的时间。

    为什么非主键索引结构叶子节点存储的是主键值？（一致性和节省存储空间）

    答：是为了方便于保证一致性和节省存储空间。

            如果在非主键索引的叶子节点也存储整行数据，这样的话在insert一个数据时就需要保证两个树结构维护完成之后才允许下面的操作，会导致在保证一致性的问题上有些复杂，并且会降低性能，还会造成数据冗余浪费存储空间。所以综合考虑之后，只在非主键索引结构中存储主键值，在通过非主键索引查询时只需要找到对应索引的主键值，在去主键索引中寻找数据即可。虽然在时间上会相比较主键索引直接查询低一些，但是避免了一致性问题和节省了存储空间。

.frm存储表结构

.MYD存储表所有的数据行

.MYI存储存储索引字段

 聚集索引（聚簇索引）就是索引和数据存储在一个文件中，innodb使用的就是聚集索引

非聚集索引（稀疏索引）就是索引和数据存储在不同文件中，myisam使用的就是非聚集索引

联合索引的底层存储结构依旧是B+树。

加入有3个字段建立联合索引，那么索引中存储的就是三个字段连接在一起的数据。

那么联合索引如何去比较大小来保证一次递增的特性呢？

通过将3个字段逐个去对比，对比的次序依赖于字段在表中的顺序。

在mysql索引中，对于null值排序，如果是单值索引并且还是Null值，不会将null值放在非叶子节点，一般会放到叶子节点块的最前面。

对于联合索引，假如1、3索引有值，2为null值，会将2为null值的索引放在索引块的最前面，相当于当作最小值处理