Spatial　index　has　been　one　of　the　active　focus　areas　in　recent　database　research.　The　R-tree　proposed　by　Guttman　is　probably　the　most　popular　dynamic　index　structure　for　efficiently　retrieving　objects　from　a　spatial　database　according　to　their　spatial　locations.　This　paper　proposes　a　new　method　of　constructing　R-tree　by　studying　every　kind　of　its　operations　thoroughly　and　combining　with　improved　k-medoids　clustering　algorithm.　Because　of　its　more　compact　structure,　the　R-tree　based　on　this　method　has　more　advantages　compared　with　traditional　R-tree.　The　results　of　the　study　show　that,　due　to　the　optimization　of　structure,　the　proposed　method　can　improve　index　efficiency　effectively.　©　2011　IEEE.