AT T R I B U T E S , I N D E X I N G , A N D Q U E R I E S
We discussed several alternative approaches for the data structure of the
index: B-trees, their variants, and hash tables. B-trees win out over hash
tables because B-trees are more scalable and because there are no unexpected
costly operations on B-trees like resizing a hash table.
The chapter then discussed the details of the BFS implementation of
B+trees, their layout on disk, and how they handle duplicates. We observed
that the management of duplicates in BFS is adequate, though perhaps not as
high-performance as we would like. Then we briefly touched on how B+trees
in BFS hook into the rest of the file system.
The final section discussed queries, covering what queries are, some of the
parsing issues, how queries iterate over indices to generate results, and the
way results are processed. The discussion also covered live queries and how
they manage to send updates to a query when new files are created or when
old files are deleted.
The substance of this chapter--attributes, indexing, and queries--is the
essence of why BFS is interesting. The extensive use of these features in the
BeOS is not seen in other systems.
Practical File System Design:The Be File System
, Dominic Giampaolo
98 5 AT T R I B U T E S , I N D E X I N G , A N D Q U E R I E S We discussed several alternative approaches for the data structure of the index: B-trees, their variants, and hash tables.