索引 为为了加速数据检索 减少磁盘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的语句。这里对于各种树并没有详细对各种树做说明，有说的不对，不详细的请指出来，万分感谢。
-----小河土。
网友评论