索引类型
- 索引按照存储结构划分为4类： B Tree（B-tree）、Hash、R-Tree、 Fulltext（MyISAM）
- 也可分为聚集索引和非聚集索引
B+tree索引
1. B Trree（B-Tree）： 有序数组+平衡多叉树
2. B+Tree：有序数组链表+平衡多叉树
B+Tree更适合排序、范围等操作。B+Tree所有的索引数组都在叶子节点上,并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针,提高了区间效率：
e.g: 范围查找,只需顺着节点和指针顺序遍历即可.而B树遍历复杂.查询复杂
平衡二叉树
平衡二叉树查找的时间复杂度是O(log2N)，查找效率和深度有关.普通的二叉树因为排序问题会退化成链表,实际复杂度是O(N).所以平衡二叉树是更好的选择
但是索引是存于索引文件中,存在磁盘上.所以比较大无法一次加到内存中,因此每次只能从磁盘中读取一个磁盘页的数据到内存.读磁盘速度很慢.所以需要找一个尽可能减少执行磁盘ID操作
B-Tree
平衡二叉树没有充分利用磁盘预读的功能（局部性原理和磁盘预读）
内存读写快,磁盘读写慢.慢很多
局部性原理：数据读取集中与使用一个数据,大概率会使用其附近的数据，而且磁盘的顺序读取效率很高，对于局部性程序来说,预读可以减少IO
磁盘预读：由于存储的特性,磁盘的存取比内存慢很多,为了提高效率,尽量减少IO,为了达到这个目的,所以磁盘读取不是按需读取,而是按页读取,一次读取一页的数据,每次加载更多的数据
红黑树：深度大,逻辑上很近的节点（父子）物理上可能很远,无法利用局部性,红黑树的IO渐进式复杂度是O(H). 平衡二叉树每次磁盘预读中很多数据都是用不上,然后深度大,进行很多磁盘IO
B树： 主要发生在内存中,二叉树发生在磁盘读取中
B+Tree
关键字存在叶子节点,非叶子节点存储索引,而叶子节点中有一个指针指向下一个也在节点.主要用来提高区间访问的性能
叶子节点按存储实际记录行,记录行想的比较紧密的存储,适合大数据量磁盘存储,非叶子节点存储记录的PK,用于查询加速,适合内存存储
非叶子节点,不存实际记录,只存储记录的key,相同内存，B+树能够存储更多的索引
索引失效
1. 查询列中有函数计算
2. like
3. 有or时，除非所有条件都加上索引
4. != or <>
5. is null 或者is not null
6. 字符串不加引号
7. 最左匹配原则
|
