多级索引：
文件系统采用多重结构搜索文件内容。设块长为512B，每个块号占3B，如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。

设块长为512B，每个块号占3B，一个物理块可放：512/3=170个目录项，即：

一个一级索引可存放的文件大小为：170×512=

一个二级索引可存放文件的大小为：170×170×512=

一个三级索引可存放文件的大小为：170×170×170×512=
混合索引：
eg1/某系统中磁盘的每个盘块大小为1KB，外存分配方法采用中的混合索引结构，其中索引节点中直接地址6项，一级索引地址2项，二级索引地址1项，每个盘块号占用4个字节，请问该系统中允许的文件最大长度是多少?

一个盘块可记录的盘块号的数量为∶1KB/4=256

直接地址∶记录6个文件所占物理块的块号

一级索引∶记录256x2=512个文件所占物理块的块号

二级索引∶记录256x256个文件所占物理块的块号

该系统中允许的文件最大长度 （256x256+256x2+6）*1KB=
eg2/存放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13 个地址项，第0～9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为4K字节，若盘块号需要用4个字节来描述，请问该系统中允许的文件最大长度是多少?

由题意可得，每个盘块最多存放4K/4=1K个盘块地址。

4K×(10＋1K＋1K×1K＋1K×1K×1K)=40K ＋4M＋4G ＋4T=

在一个采用三级索引结构的UNIX 文件系统中，假设物理块大小为1KB，用64位表示一个物理块号。主索引表含有13 个块地址指针，其中前10 个直接指向盘块号，第11 个指向一级索引表，第12 个指向二级索引表，第13 个指向三级索引表，那么，一个文件最大可有多少块？ 

A) 10 + 512 + 512^2+ 512^3 

B) 10 + 256 + 256^2+ 256^3 

C) 10 + 128 + 128^2+ 128^3 

D) 10 + 512 + 256^2+ 128^3

题目解析：物理块大小为1KB = 1024B，每个物理块占64/8 = 8B，所以一共有1024/8=128个。即一级索引有128块，那么可得二级索引有128^2块，三级索引有128^块。加上前10个直接指向的盘块，最终结果应选C。

1 真题解析
假设文件系统采用索引节点管理，且索引节点有8个地址项 iaddr[0] ～ iaddr[7] ，每个地址项大小为4B。 iaddr[0] ～ iaddr[4] 采用直接地址索引， iaddr[5] 和 iaddr[6] 采用一级间接地址索引， iaddr[7] 采用二级间接地址索引。假设磁盘索引块和磁盘数据块大小均为 1KB ，文件 File1 的索引节点如下图所示。若用户访问文件 File1 中逻辑块号为5和 261 的信息，则对应的物理块号分别为（3）， 101 号物理块存放的是（4）。

（3） A . 89 和 90   B .  89 和  136    C .  58 和 187   D .  90 和 136
（4）A .  File1 的信息   B .  直接地址索引表   C .  一级地址索引表   D .  二级地址索引表
解题的关键是会看图。图中单元格内的地址是物理块地址，而逻辑块就是空白单元格，逻辑块号没有标注出来。
首先依据题目内容，可以推出以下逻辑块号。注意：逻辑块号从 0 开始。逻辑块号 0 ~ 4，共 5 个，采用的是直接地址索引。
因为物理块每个地址项大小为 4B，磁盘索引块大小为 1KB，即 1024B。而 1024/4 = 256 个，所以一个磁盘索引块可以存放 256 个物理块地址。因此，可以就此推测出一级间接地址索引所对应的逻辑块号范围。

因为每个索引块可以存放 256 个物理块地址，所以第一个一级间接地址索引所对应的逻辑块号范围是 5 ~ 260；第二个一级间接地址索引所对应的逻辑块号范围是 261 ~ 516。具体计算步骤为：

【1】260 = 5 + 256 -1。

【2】516 = 261 + 256 -1。
所以，第一个空选 C。
块号为 101 物理地址采用的是二级索引方式，它的线连接到的是一级地址索引表，其本身存放的是二级地址索引。所以第二个空选 D。


此题涉及以下知识点。
2 文件系统物理结构
文件的物理结构是指文件在存储设备上的存放方法。文件的物理结构侧重于提高存储器的利用效率和降低存取时间。文件的存储设备通常划分为大小相同的物理块，物理块是分配和传输信息的基本单位。文件的物理结构涉及文件存储设备的组块策略和文件分配策略，决定文件信息在存储设备上的存储位置。常用的文件分配策略有：
（1）顺序分配（连续分配）
这是最简单的分配方法。在文件建立时预先分配一组连续的物理块，然后，按照逻辑文件中的信息（或记录）顺序，依次把信息（或记录）按顺序存储到物理块中。这样，只需知道文件在文件存储设备上的起始位置和文件长度，就能进行存取，这种分配方法适合于顺序存取，在连续存取相邻信息时，存取速度快。其缺点是在文件建立时必须指定文件的信息长度，以后不能动态增长，一般不宜用于需要经常修改的文件。
（2）链接分配（串联分配）
这是按单个物理块逐个进行的。每个物理块中（一般是最后一个单元）设有一个指针，指向其后续连接的下一个物理块的地址，这样，所有的物理块都被链接起来，形成一个链接队列。在建立链接文件时，不需要指定文件的长度，在文件的说明信息中，只需指出该文件的第一个物理块块号，而且链接文件的文件长度可以动态地增长。只调整物理块间的指针就可以插入或删除一个信息块。链接分配的优点是可以解决存储器的碎片问题，提高存储空间利用率。由于链接文件只能按照队列中的链接指针顺序查找，因此搜索效率低，一般只适用于顺序访问，不适用于随机存取。
（3）索引分配
这是另一种对文件存储不连续分配的方法。采用索引分配方法的系统，为每一个文件建立一张索引表，索引表中每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。索引分配既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。对一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，这时在由索引表指出的物理块中存放的不是文件而是存放文件信息的物理块地址。如果一个物理块能够存储 n 个地址，则在一级间接索引模式下，可寻址的文件长度将为【 n 的二次方 】 块。对于更大的文件可以采用二级甚至三级间接索引（例如， UNIX 操作系统采用三级索引结构）。

索引文件的优点是既适用于顺序存取，又适用于随机存取。缺点是索引表增加了存储空间的开销。
另外，在存取文件时需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。为了提高效率，一种改进的方法是，在对某个文件进行操作之前，预先把索引表调入内存。这样，文件的存取就能直接从内存的索引表中确定相应的物理块号，从而只需要访问一次磁盘。

B-Tree和B+Tree
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。
首先，对单个节点来说，是一个key value结构，key是作引的列，value有两种，对于聚簇索引来说，value就是数据，对于二级索引来说，value就是指向数据的地址。
B-Tree的结构如下：
B-tree的特点是非叶子节点上也有数据。
B+Tree是B-Tree的变体，它的结构如下：
非叶子节点的职责就是为了定位下级节点的区间，不需要存储数据。数据全部分散在叶子结点上。
B+Tree索引的优势：
由于非叶子节点不存放数据，所以可以将非叶子节点定义为固定的区间，然后可以设计每个区间的叶子结点都存放在一片固定大小的连续的内存区域，在读取的时候可以避免出现硬盘大量随机读的现象 。
Mysql中，不论是MyISAM还是InnoDB，都是使用的B+树索引，不过InnoDB使用了聚簇索引，所以索引文件和数据文件是放在一块的。MyISAM中，索引文件和数据文件是可以分开的。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字 段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为 InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用 自增字段作为主键则是一个很好的选择
ORACLE的索引，网上有的说是B-tree，但是给出图上非叶子节点又没有数据。像是B+。还有人说是B*。总之都大同小异，就不再研究了。