MySQL的几种树结构的演变历程小结

树

二叉树为了利用数组二分查找速度快的优势实现排序从而造成BST（二叉查找树），注意要造成排序，插入要按序插入
html

很明显经过按顺序插入会致使造成一个链表从而没有左分支或者右分支，缘由：一直递增或者递减。解决方法：尽量让左子树和右子树取一个平衡点，这就产生了AVL树（二叉平衡树）（严格意义上的二叉平衡树）：

按序插入会自动旋转，最大特色：最长路径和最短路径的差不超过1。但会出现这种问题：随着插入越多，每次插入致使的旋转越频繁，致使插入性能下降。好处：查找性能。应用：适合数据不频繁更改。为了使插入性能和查找性能折中，需找一个平衡点，也就是说插入性能高一点，查找性能低一点，二者差很少，这就出现了红黑树（特色：最长路径不超过最短路径的2倍）：

web

第一个图中最长路径是4，最短路径是2，再插入8时最长路径为5，旋转。红黑树也是二叉平衡树，但它不是严格意义上的二叉平衡树（相比于AVL树），是相对平衡，关键在于对最长路径和最短路径的差的定义的严格程度。也正是放松了了对最长路径和最短路径的差的定义的严格程度，红黑树插入性能提高了，毕竟相比于AVL树随着插入越多，每次插入致使的旋转就不那么频繁了。同时也致使了查找性能的降低。不只如此：红黑树还有不少为了实现使插入性能和查找性能折中的功能提供了不少限制。但仍是不能解决问题：随着插入节点愈来愈多。不管是AVL树仍是红黑树都会变得很高，I/O启动次数就很高，查找性能依然会降低。解决方法：提高每一个节点分支数，这就引出了B树：

图中演示网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html数组