平均查找长度（ASL）：在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
顺序查找，又称为线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对关键字有序的顺序表的顺序查找。
1. 一般线性表的顺序查找
一般线性表的顺序查找平均查找长度为： 。查找不成功时，与表中各关键字的比较次数显然是n+1次，从而顺序查找不成功的平均查找长度为：
顺序查找的缺点是当n较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序均可应用。同时注意，对线性的链表只能进行顺序查找。
2. 有序表的顺序查找
如果在查找之前就已经知道表是按照关键字有序的，那么当查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，这样能降低顺序查找失败的平均查找长度。
有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点所查找的长度等于它上面一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下有
有序表的顺序查找中的线性表可以是链式存储结构
折半查找，又称二分法查找，它仅适用于有序的顺序表。
折半查找的过程可用图示的二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于右子结点值。若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。
用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为约等于。折半查找的时间复杂度为，平均情况下比顺序查找效率高。该查找法仅适用于线性表的顺序存储结构，不适合链式存储结构，且要求元素按照关键字有序排序。
分块查找的基本思想：将查找表分为若干个子块。块内的元素是无序，但块之间是有序的，即第一块中的最大关键字小于第二块中的所有记录的关键字，第二块中最大的关键字小于第三块中的所有记录的关键字，依次类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
分块查找分为两步：第一步在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引块；第二步在块内顺序查找。
分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设将长度为n的查找表均匀的分布在b块，每块有s个记录，在等概率情况下：
从数据结构来讲只有2种，也就是树和树。有时候，B-树又称为B树，他们是一个东西。请注意，B-树中间的“-”是连字符，而不是“减号”。英文中是B-Tree，翻译成中文后，也就是B树，有的翻译喜欢把连字符“-”也带着，于是就成了B-树，而B-树被有些读者误读为B减树
一个树的阶，就是这个树中各个节点的子节点个数的最大值。也就是说，如果有的节点有2个子节点，有的节点有4个子节点，最多的有5个子节点，那么，这个树的阶就是5。
m阶的B树与m阶的B+树异同：
B树被设计成相对矮宽，而对B树的访问是由一系列的外存操作和内存操作交替组成的。有多少外存操作，就有多少内存操作。但要使外存操作的代价与内存操作的代价大致相当。B树能做到，而AVL与BST却做不到。
B树，又称为多路平衡查找树，B树中所有结点的孩子结点树的最大值称为B树的阶，通常用m表示。
1. B树查找
B树查找包含两个基本操作：
由于B树常存储在磁盘上，则前一个查找是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点中的信息读入内存，然后再采用顺序查找或折半查找法查找等于K的关键字
2. B树插入（插入-上溢-分裂）
将关键字key插入到B树的过程如下：
分裂的方法是：取一个新结点，将插入key后的原结点从中间位置将其中的关键字分为两部分，左部分包含的关键字放到原结点中，右部分包含的关键字放到新的结点中，中间位置的节点插入到原结点的父结点中。若此时导致父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程查到根节点为止，这样导致B树高度增加1。
分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。
插入过程和树的构建过程本质是一致的，即都是进行插入操作，并对插入后的B-树进行调整。以下面的树为基础，我们设定B-树的阶为5。用关键字序列[1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15]来构建一棵B-树。
插入10：因为最右下的节点内有5个元素，超过最大个数4了，所以需要进行拆分，把中间节点10进行提升，上升到和6一起
插入插入5、17、9、16：
插入20：插入20后，最右下节点内元素个数为5个，超过最大个数4个，所以，需要把16进行提升
插入3、12、14、18、19：
插入15：会导致13提升到根节点，这时，根节点会有5个节点，那么，根节点中的10会再次进行提升
3. B树删除（删除-下溢-合并）
当所删除的关键字不在终端结点（最底层非叶结点）时，有下列几种情况：
当被删除的关键字在终端结点中时，有下列几种情况：
以下面的树为基础，进行删除操作[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]。首先明确一下这个树的定义。它是一个5阶树。所以，每个节点内元素个数为2~4个。我们依次删除8、16、15、4这4个元素。
删除4：删除4后该节点只剩下5，需要调整。可是它的兄弟节点也都没有多余的节点可借，所以需要进行节点合并。节点合并时，方式会有多种，我们选择其中的一种即可。这里，我们选择父节点中的3下沉，和1，2，以及5进行合并。
4. B-树卫星数据
卫星数据：指的是索引元素所指向的数据记录，比如数据库的某一行。在B-树中，无论中间结点还是叶子结点都带有卫星数据。
一颗m阶B+树需满足下列条件：
无论查找成功与否，每次查找都是一条从根结点到叶子结点的路径。
注意：根结点的最大元素，也就等同于整个B+树的最大元素，以后无论插入还是删除多少元素，始终要保持最大元素在根结点中。
1. B树卫星数据
卫星数据：指的是索引元素所指向的数据记录，比如数据库的某一行。在B+树中，只有叶子结点带有卫星数据，其余中间结点仅仅是索引，没有任何数据关联。
B+树的好处主要体现在查询性能上。下面我们分别通过单行查询和范围查询来做分析。
1. 单元素查询
在单元素查询的时候，B+树会自顶向下逐层查找结点，最终找到匹配的叶子结点。比如我们查找的是元素3。
第三次磁盘IO：
B树与B+树有两点不同。首先，B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素。这就意味着，数据量相同的情况下，B+树的结构比B-树更加“矮胖”，因此查询时IO次数也更少。其次，B+树的查询必须最终查找到叶子节点，而B-树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点。因此，B-树的查找性能并不稳定(最好情况是只查根节点，最坏情况是查到叶子节点)。而B+树的每一次查找都是稳定的。.
2. 范围查询
下面我们再来看看范围查询。
B-树如何做范围查询呢，只能依靠繁琐的中序遍历。比如我们要查询范围为3到11的元素:
B+树的范围查询，则要简单得多，只需要在链表上做遍历即可：
B+树果然比B-树的中序遍历要简单得多。综合起来，B+ 树相比B-树的优势有三个：
3. B+树的特征：
4. B+树的优势：
散列表：是根据关键字而直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素个数无关。
散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称为“冲突”，这些发生碰撞的不同关键字称为同义词。
除留余数法的关键字是选好p，使得每一个关键字通过该函数转换后等待率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。
开放定址法：所谓开放地址法，指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
注意：在开放地址法中，不能随便物理删除表中已有的元素，因为若删除元素将会截断其他具有相同散列地址的元素的查找地址。所以若想删除一个元素时，给它做一个删除标记，进行逻辑删除。但是这样做的副作用是：在执行多次删除后，表面上看起来散列表很满，实际上有许多位置没有利用，因此需要定期维护散列表，要把删除标记的元素物理删除。
拉链法：对于不同关键词可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。
例如：关键字序列为，[19， 14， 23， 01， 68， 20， 84， 27， 55， 11， 10， 79]，散列函数为H(key)=key%13，用拉链法处理冲突。
装填因子：散列表的装填因子一般记为α，定义为一个表的装满程度，即：