mysql 之索引篇

 索引 为为了加速数据检索 减少磁盘IO操作 而创建的一种分散存储的数据结构。索引是由各大引擎来实现的。

索引的好处：减少存储引擎需要扫描的数据量、把随机IO变成顺序IO、帮主我们在进行分组排序的等操作的时候避免使用临时表。

普通二叉树

普通二叉树由于本身存储的特性， 会造成高瘦的这种情况， 而我们要的是矮胖，这样在查询数据的时候，才能更快找到数据。高瘦的话  层次太深了不利于查找，于是这里就出现了AVL树

平衡二叉查找树

又称AVL树

规则 左子节点 和右子节点高度差不能超过1 超过就会进行旋转 来保持两个节点之间的高度差，这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

但是这种数据结构在mysql里面还是不能满足， 因为每个节点 存放一个关键字 加上数据区 再加上子节点引用

造成的缺点：

最坏情况下磁盘的IO次数由树的高度决定，所以减少磁盘IO次数就必须压缩树的高度，让瘦高的树尽量变成矮胖的树，这样B-树就诞生了

B-树

多路平衡查找树：它在平衡二叉树的基础上做了增强。

1.数中每个节点之多有m个孩子(m>2)

2.根结点至少拥有两颗子树（存在子树的情况下）

3.除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树

4.所有的叶节点都在同一层上

如图：

        B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

B-树的特性：

1.任何一个关键字出现且只出现在一个结点中；

2.搜索有可能在非叶子结点结束；

3.其搜索性能等价于在关键字全集内做一次二分查找；

---

但是这种还是不能满足mysql的要求于是就出现了b+树B+树 可以看成是B-树的 加强版

如图：

B+树和B-树的区别：

1.B+树关键字搜索采用闭合区间

2.B+ 非叶节点不保存数据相关信息，只保存关键字和子节点的引用

3.B+ 关键字对应的数据保存在叶子节点中

4.叶子节点是顺序排列的，相邻的节点具有顺序应用关系

相比B-树的优点：

1.扫表能力强

2.磁盘读写能力强

3.排序能力更强

4.查询效率更稳定

B+树 在Myisam中B+树体现形式：

如图：

           主键索引和辅助索引都会有一个指针指向数据区， 为什么是这样存储，这是跟myisam的数据存储有关的，myisam中 索引 和数据都有一个单独文件存储。

B+树 在在Inodb中B+树体现形式:

Myisam 和Innodb 查找数据方式的区别

 Innodb 中储存数据中索引和数据都是放在一个文件中。由主键索引指针指向数据区， 其他辅助索引也都是指向主键索引的指针，也就是辅助索引每次查询都是去找主键索引然后再找到数据。如果表没有主键，Innodb 为建一个隐式的主键。

Mysiam ：数据和索引文件时单独存放的，主键和辅助索引 都是指针指向数据区的

索引相关知识补充：

1.每张表的索引 不超过5个

2.索引字段宽度尽量短

3.使用离散度高的列作为索引

4.经常用的列优先(组合索引。最左匹配）

        以上只是针对自己理解整理索引相关的知识，当然也借见其他帖子一些关于Tree的语句。这里对于各种树并没有详细对各种树做说明，有说的不对，不详细的请指出来，万分感谢。

                                                                                                                                   -----小河土。