Decentralized approaches for Web Services discovery, such as Peer-to-Peer, become more and more attentiongetting in the scientific community. In this paper, we propose a peer-to-peer framework, which adopts an enhanced Skip Graph named ServiceIndex as the overlay network for service discovery. To guarantee discovery efficiency, ServiceIndex schemed WSDL-S (Web Services Semantics) as Semantic Web Services description language and extracted its semantic attributes as indexing keys in Skip Graph. Also a multi-layer P2P overlay network was constructed to aggregate similar keys and keep load balancing on peer nodes. The evaluation showed that the ServiceIndex system performs considerable service discovery efficiency.