索引
本质上，索引是一堆有序的结构化的数据。
个人的理解，搜索的本质是查找。
查找/搜索算法（查询算法）
- 顺序查找（linear search）
时间复杂度为O(n)，在数据量很大时显然是糟糕的 -
二分查找（binary search）
时间复杂度可以表示O()=O(logn) -
二叉树查找（binary tree search）
时间复杂度：
如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为Log2(n+1),其查找效率为O(Log2n)，近似于折半查找。
如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。
一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。
- 其他
比如冒泡、哈希查找、快排等等
索引的引入
每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
(B-Tree)B树
B树本质是多路二叉树；叶节点具有相同的深度，叶节点的指针为空；所有索引元素不重复；节点中数据索引从左到右依次递增的；
减少了磁盘IO。
B树相比较平衡二叉查找树，它叉开的比较多，算是多叉平衡查找树。也就是说B树的高度要低，叉要多。如果把二叉查找树比做一个人，那么这个人是又高又有瘦，B树则是又矮又胖。
B树是一个自平衡的多叉查找树。它有以下优点:
1. 保持键值有序，以顺序遍历
2. 使用层次化的索引来最小化磁盘读取
3. 使用不完全填充的块来加速插入和删除
4. 通过优雅的遍历算法来保持索引平衡
5. 通过保证内部节点至少半满来最小化空间浪费。
6. 可以处理任意数目的插入和删除。
B+Tree
B+Tree是B树的变种。
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，可以结合存储器原理及计算机存取原理讨论为何B-Tree和B+Tree在被如此广泛用于索引。
而B+树相当于B树的升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分查找（二分查找速度不解释）。B+在基于B树的基础上又有如下优点:
- B+树的层级更少：B+树每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B+树的特点
- 每个节点中子节点的个数不能超过 m，也不能小于 m/2
- 根节点的子节点个数可以不超过 m/2，这是一个例外
- m叉树只存储索引，并不真正存储数据，这个有点儿类似跳表
- 通过链表将叶子节点串联在一起，这样可以方便按区间查找
- 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中
MySQL的索引及其数据结构
MySQL就普遍使用B+Tree实现其索引结构
总结
正因为B+树的这种特性，因此这种数据结构常用于文件系统跟数据库索引中。它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。
（完）