ABSTRAKSI: Kunci utama dalam pengembangan basis data spasial yaitu seberapa efisien query spasial tersebut ditangani, sebab pemrosesan query spasial membutuhkan biaya komputasi yang lebih tinggi dibandingkan dengan query basis data relasional biasa. Karena data spasial cenderung bersifat dinamis, besar, dan kompleks, maka dibutuhkan sebuah struktur indeks yang efisien untuk meningkatkan kinerja query spasial.
R-Tree (Rectangle Tree) merupakan salah satu struktur indeks dinamis yang digunakan dalam efisiensi pengambilan objek basis data spasial sesuai dengan lokasi spasialnya. R-tree merupakan pengembangan lebih lanjut dari B+-Tree untuk pengindeksan objek spasial yang keduanya merupakan high-balanced tree, dimana node leaf akan berada pada level yang sama.
Penelitian sebelumnya mengatakan bahwa urutan insertion dan deletion dapat mempengaruhi perbedaan struktur indeks R-tree yang terbentuk. Tugas akhir ini menguji apakah perbedaan struktur indeks R-tree yang terbentuk dari urutan insertion dan deletion yang berbeda dapat mempengaruhi performansi dari R-tree tersebut. Pengujian dilakukan dengan menggunakan query spasial yakni range search pada masing-masing skema urutan insertion maupun deletion yang berbeda.
Hasil pengujian menunjukkan bahwa urutan insertion dan deletion objek yang memperhatikan kedekatan objek pada lokasi spasialnya akan menghasilkan indeks R-tree yang lebih baik ditinjau dari overlap antar node yang dihasilkan akan lebih minimal dibandingkan dengan yang tidak memperhatikan dedekatan objek. Selain itu variasi distribusi data spasial akan berpengaruh terhadap performansi R-tree. Penyebaran data yang tergolong sangat padat akan menghasilkan performansi yang cenderung lebih baik pada proses pembentukan indeks R-tree, namun menghasilkan performansi yang buruk pada proses range search dibandingkan dengan data yang penyebarannya lebih jarang (sparse dataset).
Kata Kunci : R-Tree, spatial, indexing, urutan, insertion, deletion, query, performanceABSTRACT: One of the key issue in the development of spatial database is that how efficiently the spatial query is handled, because of processing spatial queries requires a higher computational cost compared to standard relational database queries. Because spatial data tend to be dynamic, large, and complex, an efficient index structure required to improve the performance of spatial queries.
R-Tree (Rectangle Tree) is a dynamic index structure used for efficiency in the retrieval of spatial database objects according to their spatial location. R-tree is a further development of the B+-Tree for indexing spatial objects which are both high-balanced trees, where leaf nodes will be at the same level.
Previous research claims that the order of insertion and deletion can affect the differences form of R-tree index structure. This final project will prove whether the differences form in R-tree index structure made by the different ordering of insertion and deletion may affect the performance of the R-tree. Experiments were done using the spatial query “range serach” at each different insertion and deletion ordering scheme.
The test results show that the sequence of objects that related to their spatial locations are shown to produce better performance in terms of minimal overlap produced more than the order of objects that are not related to the spatial location moreover the variation of the distribution of spatial data will affect the performance of R-tree. The distribution of data with very high dense will tend to produce better performance on constructing R-tree index, but produce poor performance on the range search as compared with dataset which object distribution is more sparse.Keyword: R-Tree, spatial, indexing, order, insertion, deletion, query, performance