前面介绍了二叉查找树(Binary Search Tree)，他对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到 lgN 的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树(Balanced Search Tree)。在一棵具有 N 个节点的树中，我们希望该树的高度能够维持在 lgN 左右，这样我们就能保证只需要 lgN 次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。本文首先介绍 2-3查找树(2-3 Search Tree)，后面会在此基础上介绍红黑树和B树。
动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度 O(log2N) 与树的深度相关，那么降低树的深度自然会提高查找效率。
今天，看到Twitter的DBA团队发布了其最新的MySQL分支：Changes in Twitter MySQL 5.5.28.t9，此分支最重要的一个改进，就是修复了MySQL 的Bug #67718：InnoDB drastically under-fills pages in certain conditions。关于此Bug的详细描述，以及如何重现此问题，可以阅读以上的Bug链接，以下简单描述下此Bug对应的问题：
在计算机科学中，trie 又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
作用于二叉查找树上的基本操作（如查找，插入等）的时间复杂度与树的高度成正比。对一个含 n 个节点的完全二叉树，这些操作的最坏情况运行时间为 O(log n)。但如果因为频繁的删除和插入操作，导致树退化成一个 n 个节点的线性链（此时即为一个单链表），则这些操作的最坏情况运行时间为 O(n) 。为了克服以上缺点，很多二叉查找树的变形出现了，如红黑树、AVL树，Treap树等。
之前我们讲到 二叉搜索树 ，从二叉搜索树到 2-3树 到 红黑树 到 B-树。
学习过了二叉查找树，想必大家有遇到一个问题。例如，将一个数组 {1,2,3,4} 依次插入树的时候，形成了如下(a)的情况。有建立树与没建立树对于数据的增删查改已经没有了任何帮助，反而增添了维护的成本。而只有建立的树如下（b），才能够最大地体现二叉树的优点。
本篇文章中，我们将介绍常见的树形结构及其常用操作的运算复杂度。
raymondCaptain 2017.11.02
2013年09月20日 16:01:26 zolalad
2017年07月14日 17:24:32 浮生忆梦
张晓龙 2016.11.22
Go的错误处理一直被吐槽太繁琐, 作为主要用GO的攻城狮, 经常写 if err!=nil, 但是如果想偷懒, 少带了上下文信息, 直接写 if err!=nil { return err} 或者 fmt.Errorf 携带的上下文信息太少了的话, 看到错误日志也会一脸懵逼, 难以定位问题.
**2016年04月29日 / elian **
在接触 redis 之前，相信很多人都有 mysql 的使用经验。
今天来分享一下Redis几道常见的面试题：
