查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找本文主要介绍比较难理解的树表查找和哈希查找。

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

1）静态查找和动态查找；

注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找。

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。

Btree创建过程详细介绍

M阶的Btree的几个重要特性：

1.结点最多含有m颗子树，m-1个关键字（m>=2）；

2.除根结点和叶子结点外，其它每个结点至少有ceil(m / 2)个子节点，ceil为上取整；

3.若根节点不是叶子节点，则至少有两颗子树。

例子：

创建一个5阶的Btree。插入的数据有：

3 14 7 1 8 5 11 17 13 6 23 12 20 26 4 16 18 24 25 19

根据Btree特性，5阶则一个磁盘空间最多有5个指针（存的查找路径 ），4个关键字(mysql存的数据)。那么具体的插入如下所示：

插入3

插入14

插入7

插入1

插入8，此时发现空间不够，这时会出现一个分裂，移动中间元素到根节点即得到如下图：

插入5

插入11,17

插入13：需要注意，此时Btree又会进行一次分裂，这分裂需要注意下13会移到根节点

后面的插入就不一一举例了，自己验证下。最后得到的这棵树如下所示：

以上操作为Btree的详细构建过程，在构建的时候主要需要注意的就是分裂，分裂后一定要判定是否符合Btree的特性，是否是一颗有序的数，左边一定小于右边，叶子节点是否已经大于阶数，叶子节点的最小数目为ceil(m(这里为5)/2)-1=2等。有时候一个数字插入的时候会进行多次分裂操作，需要特别注意。

B+Tree和BTree类似，只是B+Tree非叶子节点不会存储数据，所有的数据都存储在叶子节点，其目的主要增加了系统的稳定性。

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：

由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。

B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

哈希查找

什么是哈希表（Hash）？

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

什么是哈希函数？

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

1）用给定的哈希函数构造哈希表；

2）根据选择的冲突处理方法解决地址冲突；

常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。

3）在哈希表的基础上执行哈希查找。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

复杂度分析：

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

使用Hash

我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

欢迎关注转发评论~~~~

Btree创建过程详细介绍图文演示效果不是很好，我录制好有图文加视频配合讲解更容易理解需要的请加QQ群938837867暗号回复“555”赠送一些Dubbo、Redis、Netty、zookeeper、Spring cloud、分布式资料