P2P视频点播是继P2P文件共享、P2P直播之后，又一方兴未艾的P2P研究领域。P2P视频点播系统中的关键问题之一是如何在节点加入或播放点跳跃时迅速定位新的供应视频数据的邻居(即“邻居发现”)。迅速地发现邻居可以让节点尽快得到视频数据，让用户无需长时间等待视频开始播放，享受平滑的观看体验。当前很多商用的系统都使用集中式的定位服务器来实现节点的邻居发现，存在可扩展性问题。某些学者提出分布式邻居发现算法，尝试解决可扩展性问题，但是目前最好的算法仍需要O(log(N))或O(log(m))的时间复杂度(N是覆盖网的规模，m是视频的长度)。 在本论文中，我们为P2P视频点播系统提出一种O(l)时间复杂度的分布式邻居发现算法，命名为InstantLeap。InstantLeap算法令节点自组织形成覆盖网，作为轻量的索引结构，使得节点在加入或任何播放点跳跃的操作时进行邻居发现都只需O(l)的平均时间复杂度，不受覆盖网规模大小和视频流长度的影响，达到了理论上的最优。据我们所知，这是首次提出的P2P视频点播系统中的O(l)时间复杂度的分布式邻居发现算法。除了实现O(l)时间复杂度的理论最优性能，InstantLeap还有以下优点：实用性强，可以与现有十分流行的基于网格的流媒体协议结合；实现简单，使用统一的覆盖网，同时支持有效的流分发和邻居发现；开销小，与视频流速率相比，占用带宽仅仅不到2％。 在本论文中，我们分析比较了现有相关算法，提出层次化设计原理，给出详尽的协议设计，然后建立数学模型证明InstantLeap具有O(1)的平均时间复杂度和O(m)的平均控制开销。我们通过模拟实验评估InstantLeap，并与同类算法动态跳跃表进行比较。实验结果表明，InstantLeap比动态跳跃表减少了平均80-90％的查询次数，大幅度改善了用户体验。最后，我们对协议的各个参数的最优值进行了探索。