剑指Offer(SQL)——使用二叉查找树优化索引

先来介绍依稀二叉查找树，大家都知道二叉查找树每个节点最多只有两个子树，通常称为左子树和右子树并且左子树节点的值要小于右子树节点的值，右子树节点的值要大于父节点的值，采用这种结构会提高索引的效率，时间复杂度是(O(logn))。

上图中不仅仅是二叉查找树，也是平衡二叉树，所谓平衡二叉树就是左右子树高度的差的绝对值不超过1。

原先我们是要遍历整张表(时间复杂度是O(n))，变为折半查找后确实是提高了查询效率，但是这样是存在特殊情况的那就是让二叉树在从0开始插入的过程中，形成了线性或近似线性的二叉树，会让时间复杂度接近于O(n)，这样就会大大降低查找的效率。

这种情况下可以考虑使用自平衡二叉树(红黑树)的旋转方法，使线性二叉树经过旋转，转变为O(n)的时间复杂度，但是我们忽略掉了一个影响最大的因素——IO的读写速度。

如我们在图中去查找9，仅是这个操作就会产生三次IO操作，分别是读取硬盘中存储的5到内存，读取硬盘中存储的7到内存，读取硬盘中存储的9到内存。

因此在线性二叉树情况下性能是很低的，接下来就来优化一下所使用的方法，这个时候会想到B Tree(B-Tree)，下一篇文章将会讲到B-Tree。