Transcription

B-Tree dan Penerapan di Basis DataAldyaka Mushofan-13512094Program Studi Teknik InformatikaSekolah Teknik Elektro dan InformatikaInstitut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, [email protected] B-Tree ialah suatu struktur data yang sangatpopuler digunakan dalam pengelolaan basis data. Halini dikarenakan B-Tree dapat menampung banyak datapada tiap nodenya. Dapat perkembangannya, B-Treediterapkan dalam berbagai penanganan kasuspengelolaan basis data dan B-Tree juga dikembangkanbentuknya dalam berbagai variasi. Pada makalah ini,akan dijelaskan sedikit mengenai pemberian indekspada basis data dan B-Tree serta perkembanganpenerapannya pada zaman sekarang.Index Terms—B-Tree, Basis Data, Indexing, MediapenyimpananI. PendahuluanSekarang ini banyak kegiatan yangmenggunakan pengelolaan data. Data yang dikelolaberasal dari basis data (database). Dalampengelolaan data dari database, terdapatbermacam-macam cara, dan salah satunya ialahpemberian indeks pada database tersebut. Denganmenggunakan indeks, pencarian suatu data yangterdapat di database dapat dilakukan dengan cepat,sehingga dapat meningkatkan kinerja dalammengelola data.Dengan memberikan indeks pada data,pengelolaan data, seperti menambah, menghapus,atau memperbarui suatu data, dapat dilakukansecara mudah dan cepat. Oleh karenanya,pemberian indeks pada data merupakan hal yangsangat penting dan mendasar pada pengelolaandatabase.Pemberian indeks pada data di database-punterdapat bermacam-macam metode, salah satunyaialah menggunakan pohon. Untuk pemberianindeks menggunakan pohon dilakukan tidak secaraterurut, akan tetapi secara acak.Oleh karena itu,agar pencarian data dapat dilakukan secara cepat,maka dapat menggunakan B-Tree (Balanced Tree).B-Tree ialah pohon dengan tinggi yang sama disetiap daunnya.Gambar 1 Indeks dengan B-TreeGambar 1 menunjukkan ilustrasi pemberianindeks menggunakan pohon. Dari gambar di atasterlihat bahwa pohon tersebut di setiap daunnyamemiliki tinggi yang sama, inilah yang dinamakanB-Tree. Pada gambar di atas, terlihat bahwa setiapcabang menghubungkan suatu nilai dari lapisanatas ke nilai yang sama pada lapisan di bawahnyayang merupakan nilai terbesar pada daun di lapisantersebut. Berdasarkan metode ini, pohon akan terusmembuat lapisan hingga suatu data yang dicariditemukan. Lapisan terus dibuat hingga suatu datadapat termuat pada 1 node saja, yang kemudiandisebut daun.Gambar 2 Pencarian data 57 secara transversalII. TeoriA. IndeksSeperti yang sudah dijelaskan padapendahuluan, indeks adalah suatu cara untukmengelola suatu basis data. Indeks ialahpemberian suatu pengenal kepada data yang adadi basis data. Dengan melakukan indexing,Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014

maka kita melakukan pembuatan struktur datayang baru. Struktur data tersebut selanjutnyabertanggung jawab dalam penunjukkan datatersebut.Metode dalam pemberian indeks inibermacam-macam, mulai dari metodepemberian indeks dalam 1 lapisan hinggapemberian indeks menggunakan sub-lapis.Metode yang digunakan dalam pemberianindeks ini nantinya akan berpengaruh terhadappengelolaan basis data. Misalkan menggunakanmetode 1 lapis, bila data yang ada sangatbanyak, maka memerlukan waktu yang lamadalam pencarian data tersebut. Namun apabilatelah menggunakan metode yangmemungkinkan adanya sub-lapisan, maka datayang dicari dapat ditemukan dengan lebih cepat.Indexing merupakan hal yang sangat pentingdalam pengelolaan basis data. Apabila metodeindexing yang digunakan tidak tepat danmengakibatkan pencarian data membutuhkanwaktu yang lama, maka pengelolaan data puntidak akan maksimal dan menghabiskan banyakwaktu, namun apabila metode indexing yangdigunakan tepat, maka pengelolaan data pundapat lebih menghemat waktu dan lebihoptimal.Oleh karenanya, banyak dilakukan penilitianterhadap metode indexing demi tercapainyapengelolaan basis data yang sangat cepat danoptimal sehingga sampai saat ini struktur datayang digunakan dalam indexing cukup beragamdan banyak.B. B-TreeSalah satu struktur data yang dibuat dandigunakan untuk indexing ialah B-Tree(Balanced Tree). B-Tree ialah struktur datapohon yang tiap daunnya memiliki tinggi yangsama.B-Tree pertama kali diciptakan oleh RudolfBayer dan Ed McCreight pada tahun 1972. BTree dibuat memungkinkan untuk menyimpanbanyak data dalam satu node, jumlahsubpohonnya juga dapat sangat banyak. Karenaitulah, B-Tree sangat cocok untuk digunakandalam pengelolaan data pada disk.B-Tree dapat digunakan pada situasi dimanasebagian atau semua bagian dari pohon harusdisimpan dalam secondary storage. Hal inimemungkinkan B-Tree dapat meminimalisasijumlah akses terhadap disk.Sebuah B-Tree memiliki jumlah minimalanak pada setiap node-nya, disebut faktorminimal. Misalkan factor minimal dari suatu BTree ialah n, maka setiap node harus memilikiminimal keys sejumlah n-1.Tinggi dari B-Tree dengan jumlah key n dandegree t dapat dicari memiliki nilai𝑛 1ℎ log 𝑡2Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014Dari persamaan tersebut dapat ditentukankasus terburuk dari B-Tree sebesar O(log n).III. Operasi Pada B-TreePada B-Tree, terdapat beberapa operasi,search, insert, delete, dan create.1. Search (pencarian)Untuk mencari suatu data denganindeks yang diinginkan, maka dicariterlebih dulu suatu nilai pada node yangmemiliki nilai yang lebih besar dari nilaiyang diinginkan. Bila telah ditemukan,maka penunjuk akan menunjuk nilaisebelumnya, lalu masuk ke anak yangditunjuk oleh nilai tersebut, danmengulangi langkah tersebut hinggaditemukan. Bila pada suatu node tidakditemukan nilai yang lebih besar darinilai yang dicari, maka penunjuk akanmengikuti node yang ditunjuk oleh nilaiterbesar dari node tersebut.Dalam notasi algoritma, perintahpencarian dalam B-Tree dapat ditulissebagai berikut:i - 1while i n[x] and k keyi[x]do i - i 1if i n[x] and k keyi[x]then return (x, i)if leaf[x]then return NILelse Disk-Read(ci[x])return B-Tree-Search(ci[x], k)Kemungkinan terburuk daripencarian dalam B-Tree ialah O(logt n).2. Insert (memasukkan)Untuk melakukan perintah insert,sebelumnya harus melakukan perintahsearch terlebih dahulu untukmenentukan letak dimana data akandiletakkan. Setelah letak berhasilditentukan, maka perintah insert dapatdieksekusi. Bila node belum penuh,maka perintah insert langsung dapatdilakukan, tetapi apabila node telahpenuh, maka node harus dipecah terlebihdahulu untuk membuat node baru danmemasukkan anak baru dari nodetersebut. Bila ternyata node orangtuadari node yang akan dipecah telahpenuh, maka node orangtua tersebutharus dipecah terlebih dahulu. Perintahterus diulang hingga node tidak penuh.Dalam notasi algoritma, perintahinsert dapat ditulis seperti berikut:i - n[x]if leaf[x]

then while i 1 and k keyi[x]do keyi 1[x] - keyi[x]i - i - 1keyi 1[x] - kn[x] - n[x] 1Disk-Write(x)else while i and k keyi[x]do i - i - 1i - i 1Disk-Read(ci[x])if n[ci[x]] 2t - 1then B-Tree-Split-Child(x, i,ci[x])if k keyi[x]then i - i 1B-Tree-Insert-Nonfull(ci[x], k)Dalam perintah insert, kasus terburukmemerlukan waktu sebesar O(logt n),mengingat perintah membagi nodememakan waktu secara linear, makawaktu yang diperlukan tidak terlaluberpengaruh terhadap waktu yangdiperlukan dalam perintah insert ini.3. Delete (hapus)Dalam melakukan perintah hapus,maka banyak hal yang harusdiperhatikan. Apabila penghapusandapat mengurangi nilai key dari suatunode dan nilainya menjadi di bawahminimal nilai key, maka harus dilakukanpenyesuaian yang cukup rumit sepertipengurangan tinggi dari pohon yangmempengaruhi node-node lainnya.4. Create (membuat)Perintah create pada B-Tree akanmembuat node yang kosong. Pembuatanini dilakukan dengan mengalokasikansebuah akar baru dengan nilai keykosong dan menjadikannya daun.Perintah create dapat ditulis dalamnotasi algoritma sebagai berikut:x - Allocate-Node()leaf[x] - TRUEn[x] - 0Disk-Write(x)root[T] - xPerintah pembuatan dalam B-Treememerlukan waktu sebanyak O(l).IV. Penerapan B-Tree Pada Basis DataDalam perkembangannya, B-Tree banyakdiadaptasi dalam berbagai struktur data dalamindexing. Perkembangan ini mulai darimengembangkan B-Tree itu sendiri sampaimenggabungkan struktur data B-Tree denganstruktur data lainnya. Selain itu, penerapan B-Treejuga di berbagai macam tipe penyimpanan data.A. B-Tree Pada Flash MemoryFlash memory merupakan desain tipepenyimpanan alternatif selain harddisk. Flashmemory yang tahan goncangan, hemat energi,dan nonvolatile menjadikannya mediapenyimpanan alternatif yang populer.Pada Flash memory, B-Tree dapatdigunakan dalam pengelolaan operasi bit-wiseyang ada di Flash Transition Layer (FTL).Penggunaan B-Tree pada Flash memory inidiajukan oleh Chin-Hsien Wu, Tei-Wei Kuodan Li Ping Chang dalam makalahnya “AnEfficient B-Tree Layer Implementation forFlash-Memory Storage Systems”. Merekamengajukan untuk menggunakan B-Tree dalampengelolaan Flash Memory karena menurutmereka akses B-Tree sangat cocok dalammengelola data di Flash memory, mengingatdata yang ada di Flash memory tidak bisaditulis ulang dan jika berkeinginan untukmenulis suatu data, maka harus dilakukanpenghapusan terlebih dahulu di data yang akanditimpa. Dalam proses penghapusan inilahterdapat batasan, ketika menghapus, maka dayaguna dari flash memory ini juga berkurang,karena setiap bagian yang dapat dihapusmemiliki batas penghapusan.B-Tree nantinya akan membuat lapisan baruyang dinamakan BFTL. BFTL dapat sewaktuwaktu ditambahkan pada FTL atau dihilangkan,sesuai kehendak dari pengguna. BFTL akandiletakkan di antara lapisan file system denganFTL. Dengan adanya BFTL, B-Tree dapatmemanipulasi indeks dengan lebih leluasa. Padapenerapan B-Tree pada FTL, tidak diperlukanperubahan pada B-Tree.Menurut Chin-Hsien Wu, Tei-Wei Kuo danLi Ping Chang, BFTL dianggap sebagai bagiandari Sistem Operasi. BFTL tersusun atasreservation buffer dan node translation table.Ketika terdapat perintah menambah, menghapusatau mengubah data, maka data yang diolahialah data pada lapisan BFTL, tepatnya padabagian reservation buffer. Setelah beberapapengubahan, barunlah data tersebut kemudiandimasukkan ke flash memory. Hal ini akanmengoptimalkan masa guna dari flash memory,karena pengolahan data tidak langsung padaflash memory, akan tetapi pada lapisan BFTLterlebih dahulu, sehingga bila terdapatkesalahan atau banyak pengubahan data,mengurangi jumlah penghapusan dari blockmemory pada flash memory.Pada bagian node-translation table dariBFTL, dilakukan pengelolaan indeks. Padabagian ini, indeks dikumpulkan dan dijaga,Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014

sehingga pengelolaan indeks dapat dilakukansecara lebih efisien.B. String B-TreeString B-Tree ialah sebuah struktur datayang digunakan untuk pencarian string yangdilakukan di memori eksternal. String B-Treeini merupakan suatu penghubung antara strukturdata external-memory dan string matching.String B-Tree secara singkat merupakanpenggabungan antara B-Tree dengan percobaanPatricia pada internal-node. Dengan demikian,struktur data ini dapat menjadi lebih efektifdengan menambahkan penunjuk tambahansehingga dapat mempercepat proses pencariandan pengolahan data.String B-Tree secara teori memilikikecepatan yang sama dengan B-Tree pada kasusterburuk, akan tetapi memiliki kemampuanyang jauh lebih unggul dalam pencarian, sepertipada suffix tree. Selain itu, String B-Tree jugalebih efektif dalam pengelolaan memori utama,karena String B-Tree telah mampumengembangkan online suffix tree search padaset string string yang dinamis.Kelebihan lain dari string b-tree ialah iadapat diaplikasikan pada indexing dan duplikasiperangkat lunak. Secara singkat, String B-Treememiliki kelebihan dari B-Tree dan suffix treetetapi menghilangkan beberapa kelemahan dariB-Tree dan suffix tree tersebut.String B-Tree ini diajukan oleh PaoloFerragina dan Roberto Grossi pada makalahmereka yang berjudul “The String B-Tree: ANew Data Structure for String Search inExternal Memory and Its Application”.Mereka membuat struktur data ini karenaselama ini, perkembangan pengelolaan datapada memori eksternal sangat lamban dansemakin banyaknya data yang berupa stringyang terdapat di memori eksternal.C. iDistanceiDistance ialah salah satu penerapan daripengembangan B-Tree (B -Tree) yangdigunakan pada indexing untuk pencariantetangga terdekat (Nearest Neighbor Search)pada ruang metrik dengan dimensi yang tinggi(high-dimentional metric space). iDistancemembagi data berdasarkan strategi pembagiandata, kemudian memilih titik referensi untuksetiap bagian-bagian data tersebut. Titik-titikdata tersebut kemudian dikelompokkan kedalam satu dimensi metrik berdasarkankemiripan terhadap titik referensi yang telahdipilih sebelumnya. Hal ini menjadikan titiktitik tersebut dapat diberi indeks denganmenggunakan struktur data B -Tree dan K-Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014nearest nighbori (KNN) secara pencarian satudimensi.Penggunaan iDistance diajukan oleh H. V.Jagadish, Beng Chin Ooi, Kian-Lee Tan, CuiYu, dan Rui Zhang dalam makalah mereka“iDistance: An Adaptive B -Tree BasedIndexing Method for Nearest Neighbor Search”.Menurut mereka, iDistance merupakanstruktur data yang dapat diaplikasikan padaberbagai macam distribusi data, berbeda denganberbagai macam struktur data dengan tujuanyang sama yang hanya dapat digunakan padadistribusi data tertentu dan gagal diaplikasikanpada distribusi lainnya.Tingkat keefektifan dari struktur data inidalam pengelolaan suatu distribusi databergantung pada bagaimana data terbagi-bagi,dan bagaimana titik referensi tersebut dipilih.Teknik yang digunakan pada struktur dataini ialah dengan membagi terlebih dahulu suatudata dan menentukan titik referensi dari setiapbagian data tersebut. Setelah itu, jarak dari tiapbagian data diberi indeks. Karena jarak antarbagian data tersebut berupa angka skalar yangsederhana, maka hanya dibutuhkan sedikitupaya dalam penjagaan jarak dari data tersebut,dan B -Tree yang sederhana mampu untukmenanganinya.Pada KNN dengan query yang berpusat di q,dengan radius query sebesar r, pencarian jarakyang lebih kecil dari r dilakukan denganmengeksplorasi bagian-bagian data yang telahdibuat sebelumnya. Ini dilakukan hinggakondisi berhenti tercapai.Pembagian data yang dilakukan padaiDistance terdapat beberapa cara:a. Space-based PartitioningPembagian data dengan metode iniialah dengan membagi data yang adaberdasarkan jumlah dari ruang kosongsehingga besar/jumlah ruang kosongpada setiap bagian data sama.Dengan metode ini, dimungkinkanbeberapa titik referensi, antara lain: Pusat dari Hyperplane, jarakterdekatDengan metode ini, dihasilkanpembagian data yang memilikibentuk mirip seperti pohonpiramida (Pyramid Tree) Pusat dari Hyperplane, jarakterjauhTitik luarTitik luar yang dimaksud ialahsemua titik sepanjang garis yangdibentuk dari titik tengahhyperplane yang jatuh pada luarruang data.

b. Data-Based PartitioningSesuai dengan nama yang ada,pembagian data ini berdasarkan banyakdata yang ada, kemudian data dibagisehingga tiap bagian memiliki jumlahdata yang sama.Terdapat dua kemungkinanpemilihan titik referensi denganmenggunakan metode ini, antara lain: Pusat klusterPusat dari kluster ini selalumenjadi kandidat untuk menjadititik referensi. Sisi klusterD. Query dan Update pada B -Treeberdasarkan Indexing Moving ObjectPada struktur data ini dimungkinkan strukturdata B -Tree untuk mengelola indeks dari objekyang bergerak.Untuk dapat menjadikan B -Tree dapatmengelola indeks untuk objek yang bergerak,kita terlebih dahulu harus mampumerepresentasikan lokasi dari objek yangbergerak tersebut ke dalam fungsi lurusterhadap waktu. Selanjutnya, kita “membagi”indeks, menempatkan setiap masukan kebagian-bagian tersebut sesuai waktu.Indexing pada objek yang bergerakmenggunakan B -Tree ini diusulkan olehChristian S. Jensen, Dan Lin, dan Beng ChinOoi.V. KesimpulanDalam perkembangan dunia teknologi,pengelolaan basis data menjadi suatu hal yangsangat penting, dan salah satu metode pengelolaanbasis data ialah dengan menggunakan suatustruktur data yang disebut B-Tree (Balanced Tree).Struktur data ini banyak digunakan oleh parapengembang karena kemampuannya dalammengelola data yang sangat banyak. Dan dalamperkembangannya, struktur data ini banyakdigunakan untuk mengatasi suatu permasalahan,baik dengan mengubah struktur data ini maupuntidak.VI. Daftar Pustaka1. http://use-the-indexluke.com/sql/anatomy/the-tree, tanggalakses: 13 Desember 20132. btree.html, tanggal akses 16 Desember20133. http://www.bluerwhite.org/btree/, tanggalakses 14 Desember 20134. atabase-indexing-work, tanggalakses 16 Desember 20135. Wu, Chin-Hsien., Kuo, Tei-Wei., andChang, Li Ping. 2007. An Efficient B-TreeLayer Implementation for Flash-MemoryStorage Systems.6. Jensen, Christian S., Dan, Lin., and Ooi,Beng Chin. 2004. Query and UpdateEfficient B -Tree Based Indexing of MovingObject.7. Jagadish, H.V., Ooi, Ben Chin., Tan, KianLee., Yu, Cui., and Zhang, Rui. 2005.iDistance: An Adaptive B -Tree BasedIndexing Method for Nearest NeighborSearch.8. Ferragina, Paolo., and Grossi, Roberto.1999. The String B-Tree: A New DataStructure for String Search in ExternalMemory and Its Applications.9. Gambar 1 : http://use-the-indexluke.com/img/fig01 02 tree structure.en.svg10. Gambar 2 : http://use-the-indexluke.com/img/fig01 03 tree traversal.en.svgPERNYATAANDengan ini saya menyatakan bahwa makalah yangsaya tulis ini adalah tulisan saya sendiri, bukansaduran, atau terjemahan dari makalah orang lain,dan bukan plagiasi.Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014Bandung, 17 Desember 2013Aldyaka Mushofan, 13512094

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2013/2014 sehingga pengelolaan indeks dapat dilakukan secara lebih efisien. B. String B-Tree String B-Tree ialah sebuah struktur data yang digunakan untuk pencarian string Indexing Method for Nearest Neighbor Search”.yang dilakukan di memori eksternal. String B-Tree