很多朋友一定有很多关于mysq数据库优化的资料，主要就是索引，什么最左原则，什么用count（*），什么少用select * 等等
缘起
插入（LL，RR，LR，RL）
删除
总结
1，缘起
昨天遇到个老朋友，聊了会，他说数据库这块有没什么秘诀给他说说，他说记得我之前说“所有的一切，都是为了数据，只要把数据从哪来，到哪去，什么形式这三点弄明白了，那么一切都不会有问题”，以前没感悟，现在吃了很多亏，渐渐明白这话的意思，所以想多学点数据库方面的东西。
对于数据库的话，还是我之前的一句话“一切都是数据，一个好的数据库，结果是：处处是键。数据库设计得好，那么服务层面不会有什么大问题”。这说的键指的是，能唯一标识实体的标识（有兴趣的可以查一查“键”）。
刚好想写点什么系列的，所以就打算开一个《mysql优化原理窥探》系列，来讲解下大家常常经验而谈的mysql优化的本质到底是什么？到底为什么要这么优化？这些都是对的吗？
在这之前，我们先铺垫一些必备知识，今天就是基础，但其实也是很多人迷惑的东西。
2，插入
平衡二叉树是什么？平衡二叉树，从名字看"平衡"是核心修饰的，那平衡到底什么意思呢？意思是任意结点的深度相差不大，只能为0和1。假设一个结点BF表示该结点左子树深度减去右子树深度，那么-1=<BF<=1，这种二叉树就是平衡二叉树。
那平衡二叉树，新插入一个结点的话，也许就不满足上面BF条件了，那么这时我们就得让它变动结构，变成新的平衡二叉树。
[1]有空的子结点，无需变动结构
上图就是一颗平衡二叉树，现在新插入一个结点，应该插入到 8结点的右子树作为右结点，因为有空位置，所以插入后没有影响原来的结构，所以不用变动结构。
那什么时候会变动呢？
当然是插入后，让二叉树不再满足平衡二叉树了的时候，也即等于是，BF的绝对值不满足小于等于1。如下图
之前改二叉树为平衡二叉树，但现在插入结点 7之后，不平衡了，BF标记在了旁边，结点8和结点13 BF不满足条件了，也即不平衡了。所以需要变动二叉树的结构。
那这怎么变呢？
[2]LL类型，右旋转，再换结点
我们想一下，假设我们变动结构让结点8和结点13平衡了，再把结点动下，那么是不是就又变成平衡二叉树了？
对，这就是平衡化的本质，但怎么让结点8和结点13平衡呢？现在结点13等于2，那么让它变成1或者0是最小代价，结点8也一样。
观察上图二叉树，之前本身就是根结点左子树深度大于右子树深度，现在是在根结点的左子树的左子树插入新结点。这就是LL型。
我们再想，既然左边的深度要大一点，那我们应该是把左边的子树网右边滑，是不是就平衡了？就可以使结点8和结点13的BF小点了？(这里需要想象一下，把这些结点看成是一条铁链，绕着根结点13位置往右边滑)
向右旋转之后，得到上图，刚好BF值满足条件了，变成平衡的了。那为什么要右旋转呢？因为左子树更深，所以向右滑动。
[3]LR类型，先左旋转，再右旋转
上面的情况我们知道怎么做了，那要是是下面的图呢？
这也是根结点左子树深度要大于右子树，现在要插入新结点10，那么应该会插入到上图处结点11的左结点，但插入后，原来的平衡结构被破坏了，结点12和结点13BF分别为2和2了，那这种应该怎么办？
方法还是让结点12和结点13平衡，先断开结点12的子结点，然后以结点9向左滑动，也即向左旋转(为什么绕着结点9转，不以结点12转呢？)如下图，我们先试试
发现还是不平衡，因为结点13的BF仍为2，那就得继续滑动了，现在是左子树深度大于右子树深度，哪边小就往哪边滑动，也即是旋转，所以，我们接下来，以结点13继续向右滑动，也即向右转动，然后再调整下结点(将结点11放到结点13的左结点，将结点10放置结点9的右结点，这个具体看情况，总之让结点大于左子树的值，结点又小于右结点的值)如下图
然后，总算平衡了。其实最主要的就一点 哪边深度小，就往哪边滑动，旋转。
另外还有RR和RL类型，与上面的相反，以此类推就行了。有一点提示下，比如LL，一定是左子树深度大于右子树深度，然后插入位置是左子树的左子树，并不是左子树的左子树的左结点，是左子树的左子树就行了。
3，删除
删除的话，也需要平衡化，因为删除后如果破坏了平衡，那么也需要变动结构，使其重新平衡，具体也是上面几种类型，记住要诀:哪边子树深度小，就往哪边滑动，旋转，目的就是使两边深度相差为1或者0。
4，总结
本文主要讲解了平衡二叉树的插入的算法，插入后不平衡时，各种情况的处理办法，哪边深度小，就往哪边滑动，旋转。同反异同
你学会了吗？
点个赞吧~~~~~~
关注我，不迷路
