理解，为什么选择B+Tree做数据库的索引
-
二分查找法
在有序数组中查找某一特定元素，折半查找。O(logn)
很明显，对于无序的数据建立索引并不适合。 -
Binary Search Tree 二叉查找树
二叉查找树的时间复杂度为O(log n)，但是最坏情况下是O(n)，不平衡。
二叉查找树不适合作为索引的原因：- IO不好：平衡问题，节点数据少深度高；（AVL树，红黑树）
- 范围查找不好；
-
B-Tree B树
B树解决的问题：IO (平衡 + 节点数据多深度小)
B树没有解决的问题：范围查找 -
B+Tree
B+Tree是B-Tree的变种。
1）节点可以存放更多的key（数据地址只放在叶子节点上）
2）叶子节点双向相连接，方便范围查找。 -
B+Tree索引区别
MySQL不同的存储引擎的B+Tree索引也不太一样。
MyISAM：叶子节点存放数据的地址； 索引和数据分离
InnoDB：叶子节点存放实际的数据；
InnoDB默认按照主键的顺序来存放记录，辅助索引的叶子节点数据是相应的主键；
聚集索引：索引中键值的逻辑顺序决定了表中相应行的物理顺序。 （叶子节点存数据）
非聚集索引：索引的逻辑顺序与磁盘上行的物理存储顺序不同。 （叶子节点存地址） 备注
码农翻身学习，B+树定义好像不太一样，重在理解选择过程。
@梦工厂 2018.3.14
