Perbandingan Kinerja Pencarian Berkas pada Struktur Direktori Tingkat Tunggal dan Hierarkis

Nafisa Devi Nur Rusydah; Muhammad Ainul Yaqin

doi:10.47134/jacis.v5i2.130

Authors

Nafisa Devi Nur Rusydah Universitas Islam Negeri Maulana Malik Ibrahim Malang
Muhammad Ainul Yaqin Universitas Islam Negeri Maulana Malik Ibrahim Malang

DOI:

https://doi.org/10.47134/jacis.v5i2.130

Keywords:

struktur direktori tunggal, struktur direktori hierarkis, pencarian berkas, kinerja sistem

Abstract

Pencarian berkas yang efisien menjadi tantangan dalam sistem komputer modern karena peningkatan jumlah dan kedalaman direktori dapat memperlambat akses data. Penelitian ini membandingkan kinerja struktur direktori tingkat tunggal dan hierarkis berdasarkan waktu pencarian berkas. Metode yang digunakan berupa simulasi eksperimental pada dua struktur dengan jumlah dan jenis berkas identik (1.000 e-book). Program uji Python melakukan pencarian terhadap 100 berkas acak menggunakan Linear Search, Breadth-First Search (BFS), dan Depth-First Search (DFS), dengan sepuluh kali pengulangan. Hasil menunjukkan bahwa struktur Single-Level Directory paling efisien, dengan Linear Search mencatat rata-rata 0,002162 detik per berkas. Pada struktur Hierarchical Directory, waktu pencarian meningkat seiring kedalaman. BFS naik dari 0,007890 detik (level 2) hingga 0,080534 detik (level 5), sedangkan DFS meningkat dari 0,011600 detik (level 2) hingga 0,049423 detik (level 4). Secara keseluruhan, BFS dan DFS masing-masing sekitar 20,26× dan 17,70× lebih lambat dibanding struktur tunggal. Temuan ini menegaskan bahwa kedalaman direktori merupakan faktor utama yang memengaruhi efisiensi pencarian, sehingga struktur tingkat tunggal lebih optimal untuk pencarian berbasis pencocokan nama berkas

References

[1] M. Cai, J. Shen, B. Tang, H. Huang, dan B. Ye, “FlatFS: Flatten Hierarchical File System Namespace on Non-volatile Memories,” dalam 2022 USENIX Annual Technical Conference (USENIX ATC 22), Carlsbad, CA: USENIX Association, Jul 2022, hlm. 899–914.

[2] M. Cai, J. Shen, B. Tang, H. Huang, dan B. Ye, “Exploiting Flat Namespace to Improve File System Metadata Performance on Ultra-Fast, Byte-Addressable NVMs,” ACM Trans Storage, vol. 20, no. 1, Jan 2024, doi: 10.1145/3620673. DOI: https://doi.org/10.1145/3620673

[3] A. Dewald dan S. Seufert, “What is New in ext4 for Incident Analysis and Digital Forensics,” ERNW Enno Rey Netzwerke GmbH, Whitepaper, 2017. [Daring]. Tersedia pada: https://www.ernw.de/download/ext4_incident_analysis_digital_forensics.pdf

[4] K. Ren dan G. Gibson, “TABLEFS: Enhancing Metadata Efficiency in the Local File System,” dalam 2013 USENIX Annual Technical Conference (USENIX ATC 13), San Jose, CA: USENIX Association, 2013, hlm. 145–156. [Daring]. Tersedia pada: https://www.usenix.org/conference/atc13/technical-sessions/presentation/ren

[5] K. Ren, Q. Zheng, S. Patil, dan G. Gibson, “IndexFS: Scaling File System Metadata Performance with Table-Based Namespace,” dalam Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), ACM, 2014, hlm. 237–248. doi: 10.1109/SC.2014.25. DOI: https://doi.org/10.1109/SC.2014.25

[6] W. Lv, Y. Lu, Y. Zhang, P. Duan, dan J. Shu, “InfiniFS: An Efficient Metadata Service for Large-Scale Distributed Filesystems,” dalam Proceedings of the 20th USENIX Conference on File and Storage Technologies (FAST ’22), 2022. doi: 10.5555/3517268.3523105.

[7] Y. Zhang, G. Li, K. Lu, dan J. Wan, “PhatKV: Towards an Efficient Metadata Engine for KV-based File Systems on Modern SSD,” dalam Proceedings of the 21st International Conference on Mass Storage Systems and Technologies (MSST), 2024. [Daring]. Tersedia pada: https://www.msstconference.org/MSST-history/2024/Papers/msst24-9.3.pdf

[8] Y. Hu dan C. Wang, “Accelerating LSM-Tree with the Dentry Management of File System,” 28 September 2021, arXiv:2109.13142. doi: 10.48550/arXiv.2109.13142.

[9] J.-Y. Lee, M.-H. Kim, S. A. Raza Shah, S.-U. Ahn, H. Yoon, dan S.-Y. Noh, “Performance Evaluations of Distributed File Systems for Scientific Big Data in FUSE Environment,” Electronics, vol. 10, no. 12, hlm. 1471, Jun 2021, doi: 10.3390/electronics10121471. DOI: https://doi.org/10.3390/electronics10121471

[10] L. Jiang, Z. Zhang, R. Ni, dan M. Cai, “DirectFS: An RDMA-Accelerated Distributed File System with CPU-Oblivious Metadata Indexing,” Electronics, vol. 14, no. 19, hlm. 3778, Sep 2025, doi: 10.3390/electronics14193778. DOI: https://doi.org/10.3390/electronics14193778

[11] T. J. Khoo dkk., “Constraints on Future Analysis Metadata Systems in High Energy Physics,” Comput. Softw. Big Sci., vol. 6, no. 1, hlm. 13, Des 2022, doi: 10.1007/s41781-022-00086-2. DOI: https://doi.org/10.1007/s41781-022-00086-2

[12] H. Dai, Y. Wang, K. B. Kent, L. Zeng, dan C. Xu, “The State of the Art of Metadata Managements in Large-Scale Distributed File Systems — Scalability, Performance and Availability,” IEEE Trans. Parallel Distrib. Syst., vol. 33, no. 12, hlm. 3850–3869, 2022, doi: 10.1109/TPDS.2022.3170574. DOI: https://doi.org/10.1109/TPDS.2022.3170574

[13] K. Sitompul dan A. P. Harinja, “Rancangan Aplikasi Pencarian File pada Direktori Windows Dengan Menggunakan Metode Breadth First Search,” KAKIFIKOM J Ilmu Komput. Dan Inform., vol. 03, no. 01, hlm. 28–39, 2021, doi: 10.54367/kakifikom.v3i1.1198. DOI: https://doi.org/10.54367/kakifikom.v3i1.1198

[14] M. S. Rumetna, T. N. Lina, A. B. Santoso, R. Komansilan, dan J. B. Karay, “Implementasi Algoritma Depth First Search dalam Penyelesaian Permasalahan Lintasan dan Sirkuit Euler,” J. Komtika Komputasi Dan Inform., vol. 7, no. 1, hlm. 12–21, 2023, doi: 10.31603/komtika.v7i1.8672. DOI: https://doi.org/10.31603/komtika.v7i1.8672

[15] J. Li, “Efficient parallelism in Breadth-First Search: A comprehensive analysis and implementation,” Appl. Comput. Eng., vol. 36, no. 1, hlm. 185–191, Feb 2024, doi: 10.54254/2755-2721/36/20230443. DOI: https://doi.org/10.54254/2755-2721/36/20230443

[16] N. Purnama, “Comparative Performance Study of Search Algorithms on Large-Scale Data Structures,” J Ilm Pengetah. Dan Teknol. Komput. JITK, vol. 11, no. 1, 2022, doi: 10.33480/jitk.v11i1.6592.

[17] E. C. Da Silva, L. M. Sato, dan E. T. Midorikawa, “Distributed File System to Leverage Data Locality for Large-File Processing,” Electronics, vol. 13, no. 1, hlm. 106, Des 2023, doi: 10.3390/electronics13010106. DOI: https://doi.org/10.3390/electronics13010106

[18] S. Shaikh, “Billion-files File Systems (BfFS): A Comparison,” ArXiv Prepr. ArXiv240801805, Agu 2024, doi: 10.48550/arXiv.2408.01805.