数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构，索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引和多级索引。这里只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。这里介绍三种线性索引：稠密索引、分块索引、倒排索引。
阅读全文折半查找法
折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大)，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找，不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
阅读全文顺序查找法
顺序查找法（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，查找成功，找到查找的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不相等时，则表中没有所查的记录，查找不成功。
顺序查找的算法实现如下：
- (NSInteger)sequential_search:(NSArray *)targetArray key:(id)key {
NSInteger n = targetArray.count;
for (int i = 0; i < n; i++) {
if (targetArray[i] == key) {
return i;
}
}
return -1;
}
这段代码非常简单，就是在数组targetArray中查看有没有关键字（key），当你需要查找复杂表结构的记录时，只需要把数组targetArray和关键字key定义成你需要的表结构和数据类型即可。
对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法的时间复杂度为O(1)，最坏的情况是在最后一个位置才找到，需要比较n次，时间复杂度为O(n)，由于关键字在任何一位置的概率相同，所以平均查找次数为(n+1)/2，所以最终时间复杂度还是O(n)。
很显然，顺序查找技术是由很大缺点的，n很大时，查找效率极为地下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何的要求，在一些小型数据的查找时，是可以使用的。
