无论是折半查找、二叉排序树查找还是B树，性能都依赖于查找中的比较次数。
一种理想情况是不经过任何比较，一次直接定位索要查找的记录，即：若数据结构中存在关键字和K相等，则其必定在f(K)的存储位置上，我们称这个对应关系f为哈希函数。
冲突(Collision)：对不同的关键字，可能得到同一哈希地址，即存在key1!=key2，但f(key1)=f(key2)。此时称为冲突或碰撞。
由于在实际应用中，哈希函数都是压缩函数，所以冲突只能尽可能的减少，很难完全避免。
哈希表：根据[......]
键树，又称数字查找树(Digital Search Trees)是一棵度>=2的树，每个结点只含有组成关键字的符号。
键树有两种存储结构：
1、树的孩子-兄弟链表来表示键树。
每个Node有三个域：first指向第一棵子树的根指针；next指向右兄弟；info（可选的）记录附加数据。如下图：
查找过程是，从根结点出发，顺着first查找，如果相等，继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配，查找不成功。[......]
本文是转载的，《B树、B-树、B+树、B*树》
B树
即二叉搜索树：
1.所有非叶子结点至多拥有两个儿子（Left和Right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
如：
B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；
否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字[......]
大二那会根本没蹋下心来看，觉得天书一般，连旋转都没搞明白。
今天仔细看了书，发现真的一点不难啊，鄙视自己……
首先是概念：
平衡二叉树是为了解决前面二叉排序树不均衡的问题，而加入了一种平衡机制。所以，平衡二叉树是一种特殊的二叉排序树(BST)！
AVL树查找的平均和最差复杂度都是O(logn) ！！！(BST的最坏是O(n))
AVL树的插入复杂度是O(logn)。
平衡二叉树（简称AVL树）：对任意一个结点，它的左子树和又子树都是平衡二叉树（左子树都小于结点[......]
1、前面讨论了静态查找表，它们的特点是，数据是一次性就给好了。
2、而对于动态查找表，数据可以是在查找过程中动态添加、生成的。其实这概念不太严谨。
3、二叉排序树(BST)：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于根结点上的值。
4、二叉排序树的查找过程：
(1)若树为空，直接返回/跳出。
(2)树非空，则
(a)若key==root.data，return true。
(b)若key<root.data, root = root.left[......]