B树和B+树——应用于数据库索引

多路查找树——相比于常用的二叉树，多路查找树每个节点可以存储多个元素和多个孩子指针。主要用于做索引，来降低程序对外存磁盘设备上的数据的访问次数。

• 【2-3树】
  树中每个结点要么是2结点（即1个元素和2孩子指针或2NULL），要么是3结点（即2个元素和3个孩子指针或3NULL）。

• 【2-3-4树】
  2-3树的扩展，增加了4结点的使用。树中每个结点要么是2结点（即1个元素和2孩子指针或2NULL），要么是3结点（即2个元素和3个孩子指针或3NULL），要么是4结点（即3个元素和4个孩子指针或4NULL）。
• 都要保证所有的叶子节点都在同一层次上，即保证平衡。因此每次插入和删除结点后，都可能要对叶子节点进行调整。

B树

B树结构做索引怎么就能降低程序对外存磁盘设备上的数据的访问次数呢？

B+树——对B树的改进，使得更适用于文件系统和数据库。

【B树示例】

【B+树示例】

• 可以看到，B+树的每个分支结点中只保存了索引值，而没有保存实际的数据值。这就使得每个结点（内存页面）可以存放更多个索引元素，进一步降低了树的高度，提高了查询的效率。
• 对于B树在遍历所有元素时有重复的缺陷，B+树只要从叶子节点从左往右遍历一遍就可以，不会发生重复。

B+树作为数据库索引的实例，其中0x56等为数据实际地址

为第一列数据做索引
为第二列数据做索引

数据库索引优化策略

• 高效使用索引的首要条件是知道什么样的查询会使用到索引，即查询语句要满足B+Tree中的“最左前缀原理”时，才会使用到已经创建的索引。

• 既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。
  第一种情况是表记录比较少。
  第二种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值与表记录数的比值。越接近于1说明索引值唯一性越好，这对于B+树的维护和查询效率都很好。

• 有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。

详细的MySQL数据库索引原理和优化看这篇博文：http://blog.codinglabs.org/articles/theory-of-mysql-index.html