One minute
Week1022_share
ARTS - Share 补12.3
学技术要结合使用场景
结合场景理解技术
常常有这样的想法，学习了一段新语言、新技术，然后由于工作中没有使用，就闲置了，然后再过一段时间就忘了，等于没学。了解了一个技术实现，但是没有和实际结合起来，造成记忆不深，说明并没有完全吃透，因为没有适用场景的结合，造成知识如同空中楼阁。我建议由需求、场景引出使用这类技术的必要性，这样更能掌握技术。
比如MySQL的使用
Q: 发现MySQL查询很慢，会怎么做呢？
A: 看条件字段有没有加索引，没有的话就建立索引。
Q: 那么MySQL索引使用了什么数据结构？
A: B+树。
Q： B+树查询时间复杂度多少？
A: 和树的高度有关，大概log(n).
Q: 用hash存储索引，时间复杂度多少呢？
A: hash 是 O(1)
Q: 既然hash比B+树快，为什么MySQL还用B+树来存储索引呢？
各种树
这时候，我们就要思考下，B+树的数据结构，MySQL为什么要使用B+树。
说到树，它的基础知识就是前中后序遍历、二叉树、儿茶搜索树、平衡二叉树、红黑树、B树、B+树、、
比如红黑树，他是一个二叉树，但是有几条规则：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
根据这些定义感觉一头雾水，那么要理解它，掌握背后的设计理念、原理和解决问题的方法，比技术本身更重要。
先从二叉排序树说起。
二叉排序树是左边比根节点小，右边比根节点大, 并且左右子树都是二叉排序树。
但是有一些极端情况，插入序列是有序的，那么就会退化成链表。
所以要用平衡树，插入的同时调整这棵树，让他的节点尽量均匀分布。
红黑树就是平衡树的一种，它的复杂的定义和规则，都是为了保证数的平衡性。
为什么要保证树的平衡？因为树的查找性能取决于树的高度，让树尽量平衡，就是为了降低树的高度。
Java中TreeSet的底层就是红黑树。
再来说说B树。
B树是一种多路搜索树，他的每个节点可以拥有多余两个孩子节点。M树的B树最多拥有M个孩子节点。
为什么要设计成多路的呢？ 为了进一步降低树的高度。但是也不能无限多路，因为无限多路就是有序数组。
那么这样的结构用在哪里呢？文件系统。
但是文件系统为什么不用红黑树或者有序数组呢？
我们知道文件系统和数据库索引都是存在硬盘上的，如果数据量大的话，不能一次性加载到内存中。一棵树无法一次性加载到内存里的情况，就发现B树多路存储的威力了，每次加载B树的一个节点，然后一步步找。
于是，在内存时候，红黑树比B树效率高，但是在磁盘操作中，B树就更优了。
B+树是在B树的基础上改造，数据都集中在叶子节点，同时叶子节点之间还加了指针形成链表。
为什么要这么设计？
比如数据库一个select语句， 不止查一条，比如按照ID排序后取10条，这样的情况，如果是B树的话，需要做局部的中序遍历，可能要跨层访问，B+树都在叶子节点，不用跨层，同时又链表存在，找到首尾就可通过链表把数据取出来。
回到之前
Q： 既然hash比B+树快，为什么MySQL还用B+树。
A: 如果只选一个数据，hash更快，数据库经常查多条，由于B+树有序，索引结构有链表，那么整体会更优。数据库索引一般在磁盘上，数据量大的话没法一次装入内存，B+树可以分批加载。