简介

数据存取路径是指存取数据的位置，由于程序运行具有局部性，不可能把所有数据都调入内存，在内存中只有一部分数据，其余数据都在外存，因此数据存取路径分为辅存存取路径和内存存取路径，不同的路径，查找的方法是不同的，一般分为内存查找和辅存查找。

路径名

在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从树的根(即主目录)开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构成该数据文件的路径名(path name)。系统中的每一个文件都有惟一的路径名。

相对路径

当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据文件)为止的、包括各中间节点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进程运行时所访问的文件大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进程设置一个“当前目录” ，又称为“工作目录” 。进程对各文件的访问都相对于“当前目录”。而进行。此时各文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件，最后到达要访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形成路径名。如用户 B 的当前目录是 F，则此时文件 J 的相对路径名仅是 J 本身。这样，把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)。

绝对路径

绝对路径是指目录下的绝对位置，直接到达目标位置，通常是从盘符开始的路径。

完整的描述文件位置的路径就是绝对路径，以web站点根目录为参考基础的目录路径。绝对路径名的指定是从树型目录结构顶部的根目录开始到某个目录或文件的路径，由一系列连续的目录组成，中间用斜线分隔，直到要指定的目录或文件，路径中的最后一个名称即为要指向的目录或文件。之所以称为绝对，意指当所有网页引用同一个文件时，所使用的路径都是一样的。

内存查找方法

顺序查找

顺序查找(sequential scarch)又称线性查找，是‘种最简单的查找方法。它是指将数据以线性表的形式存储，用线性表来表示静态查找表。其基本思想是：从线性表中第一个记录开始，依次比较每个数据元素的关键字，若记录的关键字与给定值相等，则查找成功返回该元素序号；若查完整个线性表都没有与给定值匹配的元素，则查找失败。

复杂度分析：

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

折半查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；