随着互联网和多媒体技术的迅速发展，人们可以访问到的视频数据急剧增长，如何从这些海量的数据中寻找感兴趣的内容成为一个非常重要的研究课题。通常，人们利用特征提取算法从多媒体数据对象中提取出特征矢量，然后利用特征矢量之间的距离表示多媒体对象之间相似度，从而利用相似性检索，通过计算查询矢量与数据库中矢量之间的距离找出满足条件的对象。由于这些特征矢量通常维数较高，且当数据库中矢量很多时，简单的顺序扫描搜索将导致极大的查询代价，无法满足用户需求。为了提高查询效率，就必须借助于高效的、适合高维数据的索引结构。　　 近几十年中，人们提出了很多高维数据索引结构，如R-Tree、M-Tree及其变种等。这些索引结构在维数升高时性能会急剧下降，即产生所谓的“维灾”。另外，目前的很多索引结构都是适用于维数一定的数据，当多媒体系统中同时存在不同维度的特征矢量时，其查询性能也受到影响。　　 本文对现有的索引结构进行了研究。已有的NB-Tree(Norm B+-Tree)方法通过计算特征矢量与参考点的距离将高维特征矢量映射到一维距离空间，采用大型数据库系统所支持的B+-tree进行索引，通用性强且易于维护。但NB-Tree未考虑数据分布情况，使得相似查询的候选结果集中存在很多脏数据，增加了不必要的距离计算次数。结合已有的NB-Tree改进方法，本文从数据分布的角度出发，改进出INNB-Tree(Improved New NB-tree)。INNB-Tree采用主成分析原理选择landmark点的方法来选择参考点，增大了一维距离值之间的差异，从而减少了相似查询时需要比较的数据量。同时，结合特征矢量间的偏移角，剔除了由空间位置不相关产生的脏数据，减少了距离计算次数。对比实验结果表明，该方法性能较好。　　 最后，从应用的角度出发，结合道路视频导航系统，利用INNB-Tree建立索引，提高检索效率，证明了该索引结构在实际应用中具有可行性。