Basis Data Spasial dapat menyimpan data yang berhubungan dengan objek dalam ruang meliputi titik garis, dan poligon. Basis Data Spasial mempunyai beberapa Database spasial memiliki beberapa jenis proses pencarian, salah satunya adalah Nearest Neighbour. Nearest Neighbour adalah query yang dapat memperkirakan titik terdekat untuk menemukan objek. Namun, Nearest Neighbour memiliki kelemahan. Saat komputasi hasil pencarian memakan waktu yang lama. Namun hal ini dapat diatasi dengan menggunakan ruang partisi yaitu Diagram Voronoi. Namun, metode tersebut terdapat kekurangan karena objek pada fragmentasi tidak dapat secara langsung diakses. Metode indeks dapat mengoptimalkan atau mengurangi objek yang akan diperiksa pada proses query. Salah satu struktur indeks yang paling banyak diusulkan untuk mengindeks data spasial adalah R-Tree. R-Tree adalah salah satu varian R-Tree yang memperbaiki penanganan overflow. R-Tree dapat mengoptimasi area, margin dan overlap sehingga ruang lingkup direktori akan memberikan performa pengindeksan yang optimal. Dalam tugas akhir ini akan dilakukan pengindeksan pada Highest Order Voronoi Diagram dengan metode R*-tree. Dengan membagi wilayah partisi dengan MBR. MBR secara rekursif dikelompokkan menjadi MBR yang lebih besar untuk membentuk tree, dimana MBR mencakup semua objek spasial secara terus menerus. Dengan menggunakan metode ini akan meningkatkan kinerja pencarian untuk menemukan suatu wilayah pada suatu objek.