BST Introduction

Ini bukan rahasia untuk seorang desainer sistem database yang mengalami kesulitan dan hanya memerlukan beberapa aplikasi saja untuk menyelesaikan masalahnya. Diantaranya adalah reliability, proteksi, integritas, implementasi, dan pilihan bahasa query. Pada halaman ini kita akan mencoba untuk memeriksa masalah yang harus dihadapi oleh oleh desainer database (selagi mengingat masalah diatas tadi): design dari sebuah sistem database yang difasilitasi respon waktu pencarian yang cepat dari beberapa query yang berbeda. Kita akan membatasi perhatian ke database untuk "menetapkan jumlah record tanpa pointer"; secara khusus kita asumsikan bahwa kita harus mengatur sebuah file dari N record, yang dimana setiap record tersebut terdapat kunci k. Banyak penelitian sebelumnya yang sudah dilakukan untuk mengatasi masalah pada batasan ini; pembaca yang tertarik untuk diskusi dengan pendapat yang berbeda yaitu Lin, Lee, dan Du [1976], Rivest [1976], dan Wiederhold [1977]. Pada halaman ini kita akan memeriksa struktur data tertentu, multidimensional binary search tree, untuk disesuaikan sebagai alat pada implementasi database. multidimensional binary search tree (disebut k-d tree ketika terdapat kunci k didalam sebuah record) yang diperkenalkan oleh Bentley [1975]. k-d tree adalah generalisasi alami yang biasa dikenal dengan binary search tree untuk menangani rekaman tunggal yang memiliki banyak key. Ini adalah struktur yang sangat menarik dari sudut pandang desain database karena mudah untuk di implementasikan dan memungkinkan beberapa macam query terjawab dengan efisien. Eksposisi asli k-d tree ketika digunakan untuk istilah geometris, dan sejak saat itu k-d tree telahj digunakan untuk menyelesaikan nomor dari  permasalahan "geometris" database yang timbul dalam data analisis dan statistik. Tujuan dibuatnya jurnal ini adalah untuk menggunakan k-d tree dalam database, untuk mendapatkan hasil dalam k-d tree yang terlihat sejak struktur diperkenalkan, dan memperlihatkan bagaimana struktur basis data dapat dirubah untuk fasilitas implementasi database dalam skala besar (dan sangat besar). sejak k-d tree menjadi generalisasi alami dari standar binary search tree kita akan melakukan review terhadap data struktur yang dikenal pada Section II. di Section III kita mengembangkan k-d tree. Kita menjelaskan dimana perbedaan dari pencarian yang bisa dilakukan di Section IV dan membicarakan maintenance dari k-d tree pada Section V. Section VI menghadapi masalah dalam implementasi k-d tree pada media penyimpanan yang berbeda, dan mencari contohnya kemudian diperiksa pada Section VII. Petunjuk lebih lanjut dan kesimpulan terdapat pada Section VIII dan IX.