内查找和外查找：都在内存中查找即内查找，外查找还涉及外存，比如硬盘等。
分类包括：
1、线性表的查找
又分顺序查找、二分查找和分块查找。
1）二分查找又叫折半查找
- 折半查找要求线性表有序。
- 有序是指存在某个关键字的序列。
- 基本思想是拆半。
- 二分查找可以用二叉树来描述，按照二分查找的思想建立一棵二叉树，此树称为二分查找的“判定树”。
- 二分查找的最坏性能和平均性能相近。
2）分块查找
线性表分成块，每块内部不要求有序，但块块之间应有序
2、树表查找
1）二叉排序树
- 左子树非空，则左树上所有节点均小于根。
- 右子树非空，则右树上的所有节点均大于根。
- 左右子树分别仍是二叉排序树
- 二叉排序树中的“中序遍历”是递增序列。
- 同一序列，构成的二叉排序树可能不同。
2）平衡的二叉排序树
- 要求二叉排序树的左子树和右子树的高度最多相差1
- 这个差被成为平衡因子
- 平衡二叉树避免了顺序查找行为的出现。
3）B树
前面方法都只适用于内查找，B树则适合外查找。
B－树是平衡二叉树的一种。
定义一个m阶的B树
- 每个节点至多有m个孩子
- 根节点有两个孩子或者为空
- 每个节点至少有（m/2的上限）个孩子（除了根和叶）。
- 叶在同一层，且叶中没有关键信息。
- 有K个孩子的非叶节点恰好有k-1个关键字。
查找B树时，给定关键字的查找首先从根开始，一定能确定要找的K在Ki和Ki+1之间。在这之间重复寻找，直到成功或者返回指针为空。
文件系统NTFS对目录索引的管理使用B树。