MySQL 索引
refer:
-
- B-Tree/B+Tree的详解： http://blog.csdn.net/v_july_v/article/details/6530142
索引是一种数据结构，以文件的形式存储着
- 它有一个一个的节点组成. 每一个节点，会对应磁盘上的一个 页(page)
- 查询的效率，跟节点的数量有关. 节点越少，查询所用的时间越少
- 在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复
- MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址
- InnoDB要求table都有主键，如果没有，会创建一个隐式的主键
- MyISAM：主键跟辅助索引，结构是一样的
- InnoDB: 辅助索引，存的是主索引的地址, 所以不宜使用 过长的字段作为主键, 否则辅助索引会变得很长，索引的节点会增多
- 数学计算，会让索引失效
- 建议使用自增的数字作为主键.
因为这样在插入的时候，数据项就会在已有的基础上进行添加，否则有可能在已有的数据项中间插入，从而会引起裂变
阶，指的是，该B-Tree中的节点最多可以包含多少个子节点
一个m阶的B-Tree，会有如下特性
1. 该树中的每一个节点，最多只能拥有m个子节点
2. 每一个非叶子节点(除了根节点)，至少含有 [m/2]个子节点 ( 函数[m/2]的意思是，向上取整)
3. 如果根节点不是叶子节点，那么它至少会有2个子节点
4. 一个非叶子节点，如果用有 k个子节点，那么该节点必须包含 k-1个 key。
即：
节点的子节点数目 = 节点的关键字数+1
5. 所有的叶子节点，都只能出现在同一个 层级，不能出现在不同的层级上
如果一个节点，有3个子节点，那么，它必须有两个key，比如是： a1, a2
- 最左边的子节点的值，都会小于a1
- 中间的子节点的值，在 a1 与 a2之间
- 最后边的子节点的值，会大于 a2
B+Tree
-
有n个子节点的节点，含有n个key (B-Tree 是，n-1)
-
只有叶子节点，才包含了key的全部信息，比如key所指向的Data的指针，也只有通过叶子节点才可以找到key所指向的真正的完整数据 (B-Tree的叶子节点并没有包含全部需要查找的信息)
-
所有的叶子节点的Key，会自动的组成一个从小到大排列的 有序链表
-
所有非叶子节点，只是包含子节点的最大或者最小的key值 (B-Tree,非叶子节点也包含key所指向的数据的指针信息)
B+Tree的结构示意图如下：
3、B+Tree与B-Tree 的区别
1）B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。
2）在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好，而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B+树的性能可能还会好些，而且B+树的叶子节点使用指针连接在一起，方便顺序遍历（例如查看一个目录下的所有文件，一个表中的所有记录等），这也是很多数据库和文件系统使用B+树的缘故。
思考：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？
- B+树的磁盘读写代价更低 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
- B+树的查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。