96
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
OR node
name == Query.txt
name == Indexing.txt
Figure 5-6 The parse tree for an OR query.
Unfortunately this obviates any benefit of B+trees and is much slower than
doing a normal B+tree search. It is what end users expect, however, and that
is more important than the use of an elegant B+tree search algorithm.
Additional Duties for Read Query
The read query routine also maintains additional state because it is repeat-
edly called to return results. The read query routine must be able to restart
iterating over a query each time it is called. This requires saving the posi-
tion in the query tree where the evaluation was as well as the position in the
B+tree the query was iterating over.
Once a particular leaf node exhausts all the files in that index, the read
query routine backs up the parse tree to see if it must descend down to
another leaf node. In the following query:
name == Query.txt
|| name == Indexing.txt
the parse tree will have two leaves and will look like Figure 5-6.
The read query routine will iterate over the left half of the query, and when
that exhausts all matches (most likely only one file), read query will back up
to the OR node and descend down the right half of the tree. When the right
half of the tree exhausts all matches, the query is done and read query returns
its end-of-query indicator.
Once the query engine determines that a file matches a query, it must be
returned to the program that called the read query routine. The result of a file
match by the query engine is an i-node (recall that an index only stores the
i-node number of a file in the index). The process of converting the result of a
query into something appropriate for a user program requires the file system
to convert an i-node into a file name. Normally this would not be possible,
but BFS stores the name of a file (not the complete path, just the name) as an
attribute of the file. Additionally, BFS stores a link in the file i-node to the
directory that contains the file. This enables us to convert from an i-node
address into a complete path to a file. It is quite unusual to store the name of
a file in the file i-node, but BFS does this explicitly to support queries.
Practical File System Design:The Be File System
, Dominic Giampaolo
page 96