mysql-索引
一、索引是什么?
索引是帮助MySQL高效获取数据的数据结构。
二、索引能干什么?
索引非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。索引能够轻易将查询性能提高好几个数量级，总的来说就是可以明显的提高查询效率。
三、索引的分类?
1、从存储结构上来划分：BTree索引（B-Tree或B Tree索引），Hash索引，full-index全文索引，R-Tree索引。这里所描述的是索引存储时保存的形式，
2、从应用层次来分：普通索引，唯一索引，复合索引
3、根据中数据的物理顺序与键值的逻辑（索引）顺序关系：聚集索引，非聚集索引。
B树
B树中，每个结点中关键字从小到大排列
B树 都取在内存中查询
B-Tree 特性
关键字集合分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
自动层次控制；
B-Tree搜索原理
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
因此，B-Tree的查找过程是一个顺指针查找结点和在结点的关键字中进行查找的交叉进行的过程。
B-Tree 插入
B-树是从空树起，逐个插入关键码而生成的。
在B-树，每个非失败结点的关键码个数都在[ m/2 -1, m-1]之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入。
B Tree(B-Tree变种)索引可存16KB
B 树可以看作是B树的一种变形，在实现文件索引结构方面比B树使用得更普遍。
B Tree与B-Tree区别
1 非叶子节点不存储data 只存储索引（余）可以放更多的索引
2叶子节点包含所有索引字段(所有关键字都在叶子结点出现)
3叶子点用指针连接，提高区间的访问的性能(为所有叶子结点增加一个链指针)
4非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i 1])的子树（B-树是开区间）；
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；
对B 树进行两种搜索运算
循叶结点链顺序搜索
另一种是从根结点开始，进行自顶向下，直至叶结点的随机搜索。
B Tree的优势
1、更加高效的单元素查找
a、首先B 树的中间节点不存储data，所以同样大小的磁盘页可以容纳更多的节点元素，如此一来，相同数量的数据下，B 树就相对来说要更加矮胖些，磁盘IO的次数更少。
b、由于只有叶子节点才保存data，B 树每次查询都要到叶子节点；而B树每次查询则不一样，最好的情况是根节点，最坏的情况是叶子节点，没有B 树稳定。
2、叶子节点形成有顺链表，范围查找性能更优