427 lines
11 KiB
Groff
427 lines
11 KiB
Groff
.TH search "" "" "/rdb Command"
|
|
.PC "Search a table"
|
|
\fBsearch [-m[bhirs]] [\-hsnx +x] [\-l [2> \fIlocation\fB]] \fItableorlist \fB[\fIkeycolumn ...\fB] [ < \fIkeytable\fB ]\fR
|
|
.PP
|
|
.II "row^find quickly"
|
|
The command
|
|
.B search
|
|
finds a row quickly.
|
|
It searches
|
|
.I tableorlist
|
|
for each row in which the value
|
|
.I keycolumn
|
|
matches one or keys you supply.
|
|
The key or keys can either be entered interactively,
|
|
or read from
|
|
.IR keytable .
|
|
You must use the
|
|
.B /rdb
|
|
command
|
|
.B index
|
|
to index
|
|
.I tableorlist
|
|
before you can use
|
|
.B search
|
|
to search it.
|
|
.PP
|
|
By default, a key's value must match exactly the string within
|
|
.IR keycolumn .
|
|
The options
|
|
.B \-x
|
|
and
|
|
.B +x
|
|
modify this behavior; they are described below.
|
|
.PP
|
|
You can use
|
|
.B search
|
|
in any of several different ways.
|
|
Because it reads the key values from the standard input,
|
|
you can input the keys by typing them interactively at the terminal,
|
|
by diverting the contents of
|
|
.I keytable
|
|
into it,
|
|
or by piping the output of a command into it.
|
|
Each method is demonstrated in the examples given below.
|
|
Therefore, it is easy to use
|
|
.B search
|
|
on a command line or in a shell script.
|
|
For example, the command
|
|
.B domain
|
|
is a shell script that uses
|
|
.B search
|
|
to speed its searches.
|
|
If you use a pipe to pass data to
|
|
.BR search ,
|
|
think of a stream of keys going into it
|
|
and a stream of matching rows coming out.
|
|
.PP
|
|
.B search
|
|
can use a number of different methods of searching.
|
|
There are advantages and disadvantages to each;
|
|
different sizes and structures of tables are best suited to different
|
|
methods of searching.
|
|
If you are not sure which method to use, you can try them all
|
|
on your
|
|
.IR tableorlist .
|
|
Use the COHERENT command
|
|
.B time
|
|
to find how long each method takes, then pick the one that
|
|
runs the fastest.
|
|
Another
|
|
.B /rdb
|
|
command,
|
|
.BR timesearch ,
|
|
runs each form of
|
|
.B search
|
|
on the sample
|
|
.BR unixtable ,
|
|
which is kept in directory
|
|
.BR $RDB/demo .
|
|
Because
|
|
.B timesearch
|
|
is a shell script, you can modify it to time the different methods
|
|
for your own file.
|
|
.PP
|
|
The behavior of
|
|
.B search
|
|
depends upon which method of searching you choose.
|
|
With some methods, it first searches
|
|
another table (called the ``secondary index file'')
|
|
built by the command
|
|
.BR index .
|
|
One method, sequential, searches every row in
|
|
.IR tableorlist .
|
|
.PP
|
|
If you change
|
|
.IR tableorlist ,
|
|
such as when you add a new row or delete an old one, you must reindex it.
|
|
If you develop application programs, you can have them update
|
|
secondary index files to handle dynamic file-processing.
|
|
.SH "Methods of Searching"
|
|
The following describes the different methods of searching a table.
|
|
Each method is introduced by the command-line option with which
|
|
you can invoke it:
|
|
.IP \fB\-m\fR
|
|
.II "search^sequential
|
|
Perform a sequential search.
|
|
This is the default method.
|
|
.IP \fB\-mb\fR
|
|
.II search^binary
|
|
Binary search.
|
|
This first looks at the middle record of the file.
|
|
If the key column's value is greater than that of the key that
|
|
.B search
|
|
is seeking, then
|
|
.B search
|
|
look at the record one quarter of the way through the file.
|
|
.B search
|
|
continues to bifurcate the table until it finds the row, or finds
|
|
that the row is not there.
|
|
.sp \n(pDu
|
|
The method of searching
|
|
requires that you first sort the table on the key column.
|
|
.sp \n(pDu
|
|
A binary search takes log(2)\fIn\fR accesses:
|
|
.DS
|
|
.ta 1.0iC 2.5iC
|
|
\fIAccesses No. of Records\fR
|
|
10 1 thousand
|
|
20 1 million
|
|
30 1 billion
|
|
40 1 trillion
|
|
.DE
|
|
.sp \n(pDu
|
|
Binary searching is a good method for searching tables
|
|
that must remain sorted on the key column.
|
|
.IP \fB\-mh\fR
|
|
.II search^hash
|
|
Hash searching.
|
|
A hash search computes an address from the key and
|
|
looks into a secondary file at that address.
|
|
If the key matches,
|
|
it retrieves the address of the row you want in the main file and then
|
|
retrieves it.
|
|
If the address
|
|
.B search
|
|
hashes to is empty (i.e., has a value of zero),
|
|
then the key does not match and the row is not in the file.
|
|
.sp \n(pDu
|
|
Occasionally, another key is there that happens to hash
|
|
to the same address;
|
|
this is called a
|
|
.IR collision .
|
|
When a collision occurs,
|
|
.B search
|
|
will keep looking at
|
|
subsequent entries in the secondary table until
|
|
it either finds a match or finds an empty or deleted (\-1) entry.
|
|
.sp \n(pDu
|
|
A hash search usually takes two disk accesses when the
|
|
hash table is half full.
|
|
For this reason,
|
|
.B /rdb
|
|
sets up hash tables that are twice as large as the number
|
|
of records being hashed.
|
|
As the data table grows, it must be reindexed to keep the hash speed up.
|
|
.sp \n(pDu
|
|
Hashing is a good method for tables that are static or change only rarely.
|
|
.IP \fB\-mi\fR
|
|
.II search^inverted
|
|
.II search^indexed
|
|
Inverted or indexed searching.
|
|
An inverted search uses a secondary file that must have been created by
|
|
.BR index .
|
|
This index table has two columns:
|
|
the key column from the data table, sorted to allow binary searching;
|
|
and the offset of each key-column value within the data table.
|
|
When
|
|
.B search
|
|
finds the key in the index table's key column, it then uses value from
|
|
the address column to retrieve the row from the data table
|
|
in a single disk read.
|
|
The inverted method takes a little longer than binary,
|
|
but sorting the index file is much faster than sorting the data table.
|
|
.IP \fB\-mr\fR
|
|
.II search^record
|
|
Record number searching.
|
|
A record search simply retrieves the row requested.
|
|
For example, if you enter `5', you will get the fifth row in the data table.
|
|
.sp \n(pDu
|
|
To retrieve a record by its row number,
|
|
.B search
|
|
reads a secondary file that
|
|
that contains the offset for each record in the data table.
|
|
The record method is a faster way to retrieve a record;
|
|
however, you must know the number of the record you want, and you must
|
|
either keep the data table in that order, or reindex it.
|
|
You can use the command
|
|
.B replace
|
|
to move a row to the of its table and update the secondary
|
|
index to point to the row's new location.
|
|
.IP \fB\-ms\fR
|
|
.II search^sequential
|
|
.II search^linear
|
|
Sequential or linear searching.
|
|
A sequential search examines all records in
|
|
the data table in the order in which they appear.
|
|
It is not a fast-access method, although it may
|
|
still be faster than that used by the command
|
|
.BR row .
|
|
It is provided as a benchmark for timing other methods.
|
|
If your file is not big enough to
|
|
make the other access methods worthwhile, just use sequential
|
|
.B search
|
|
or
|
|
.B row
|
|
and save yourself the overhead of building and maintaining an index.
|
|
.sp \n(pDu
|
|
A sequential search can search multiple key columns, and and can search
|
|
any column.
|
|
.II grep
|
|
The sequential method is better than the COHERENT command
|
|
.B grep
|
|
because it looks at one column, whereas
|
|
.B grep
|
|
scans the entire row for a pattern match.
|
|
.SH "Other Options"
|
|
.B search
|
|
also recognizes the following command-line options:
|
|
.IP \fB\-h\fR
|
|
Do not print the table's head line.
|
|
By default,
|
|
.B search
|
|
prints the head line of the table it searches as well as all rows it finds.
|
|
The \fB\-h\fR option suppresses the printing of the head line
|
|
and prints only the rows you are seeking.
|
|
.IP \fB\-l\fR
|
|
Output the location of the record in the data table
|
|
and the location of the index record in the index table.
|
|
.II replace
|
|
.II lock
|
|
.II unlock
|
|
These locations is in the form
|
|
.IR from to xfrom xto" ,
|
|
and can be piped to the commands
|
|
.BR replace ,
|
|
.BR lock ,
|
|
and
|
|
.BR unlock .
|
|
.B search
|
|
writes these data to the standard-error device,
|
|
to separate them from the table it writes to the standard output.
|
|
.sp \n(pDu
|
|
Because
|
|
.B search
|
|
is a shell program, it demonstrates how you can do this in your own programs.
|
|
Turning on this option also turns on the
|
|
.B \-s
|
|
option because
|
|
.B /rdb
|
|
allows you to lock or replace one record at a time.
|
|
Therefore, all keys in your file must be unique, or
|
|
some will never be found.
|
|
.IP \fB\-s\fR
|
|
Search for only one row.
|
|
This speeds the search because
|
|
.B search
|
|
quits when it finds the first match and continue searching the file.
|
|
.IP \fB\-x\fR
|
|
Partial match and case insensitive, like the Berkeley command \fBlook\fR.
|
|
.IP \fB+x\fR
|
|
Exact match, including blank characters.
|
|
The default matching ignores blank characters.
|
|
.SH Examples
|
|
Assume you have a file called
|
|
.BR inventory ,
|
|
which appears as follows:
|
|
.DM
|
|
Item Amount Cost Value Description
|
|
---- ------ ---- ----- --------------
|
|
1 3 50 150 rubber gloves
|
|
2 100 5 500 test tubes
|
|
3 5 80 400 clamps
|
|
4 23 19 437 plates
|
|
5 99 24 2376 cleaning cloth
|
|
6 89 147 13083 bunsen burners
|
|
7 5 175 875 scales
|
|
.DE
|
|
.PP
|
|
If you had indexed the column
|
|
.BR Description ,
|
|
then you have several ways to find rows:
|
|
.IP \fB1.\fR 0.3i
|
|
Interactively type key values.
|
|
.B search
|
|
immediately prints the rows it finds.
|
|
For example, type:
|
|
.DM
|
|
search -mh inventory Description
|
|
.DE
|
|
.sp \n(pDu
|
|
.B search
|
|
responds with the head line of the inventory table.
|
|
Now you can type names, in this example
|
|
.BR scales ;
|
|
if
|
|
.B search
|
|
finds a match, it returns the row that contains the key.
|
|
.IP \fB2.\fR
|
|
Divert a table or list file to
|
|
.BR search .
|
|
You can create a table with a column of key values; for example:
|
|
.DM
|
|
Description
|
|
-----------
|
|
scales
|
|
clamps
|
|
.DE
|
|
.sp \n(pDu
|
|
The following command line diverts this table into
|
|
.B search
|
|
.DM
|
|
search -mh inventory Description < description
|
|
.DE
|
|
.sp \n(pDu
|
|
and produces the following output:
|
|
.DM
|
|
Item Amount Cost Value Description
|
|
---- ------ ---- ----- --------------
|
|
7 5 175 875 scales
|
|
3 5 80 400 clamps
|
|
.DE
|
|
.IP \fB3.\fR
|
|
Input keys through a COHERENT pipe.
|
|
For example, the command
|
|
.DM
|
|
column Description < sometable | search -mh inventory | column Value
|
|
.DE
|
|
.sp \n(pDu
|
|
returns the following:
|
|
.DM
|
|
Value
|
|
-----
|
|
875
|
|
400
|
|
.DE
|
|
.sp \n(pDu
|
|
If you wish to justify a table like this, just pipe the output of
|
|
.B search
|
|
to the command
|
|
.BR justify .
|
|
.sp \n(pDu
|
|
This lets you use the COHERENT command
|
|
.B echo
|
|
to pipe a key value:
|
|
.DM
|
|
echo scales | search -mh inventory Description
|
|
.DE
|
|
.sp \n(pDu
|
|
which returns the following to the standard output:
|
|
.DM
|
|
Item Amount Cost Value Description
|
|
---- ------ ---- ----- --------------
|
|
7 5 175 875 scales
|
|
.DE
|
|
.PP
|
|
In shell programming, you can capture the output of a program
|
|
or a pipe by putting it within two grave (`) symbols.
|
|
In a shell script, you can set an environmental variable like this:
|
|
.DM
|
|
RECORD=`echo key | search -mh -h bigtable column`
|
|
.DE
|
|
.PP
|
|
The command
|
|
.B "echo $RECORD"
|
|
displays the data diverted into this variable; for example:
|
|
.DM
|
|
7 5 175 875 scales
|
|
.DE
|
|
.PP
|
|
Now the
|
|
.B RECORD
|
|
environmental variable is equal to the matching row in the table.
|
|
Note the
|
|
.B \-h
|
|
is important to keep the head line from being written into
|
|
.BR RECORD .
|
|
.SH "Search vs. Select"
|
|
.B search
|
|
is important for application programs written in
|
|
shell scripts, the C programming language, or other code.
|
|
It can be used interactively, but the command
|
|
.B row
|
|
is much more powerful because it can seek combinations of logical conditions,
|
|
regular expressions, and conditions such as
|
|
.I "greater than,"
|
|
whereas
|
|
.B search
|
|
needs a key (either exact or partial).
|
|
But for pulling a row out of a big table,
|
|
.B search
|
|
can speed things up enough to be preferred.
|
|
In summary,
|
|
.B search
|
|
is for high-speed access with keys, whereas
|
|
.B row
|
|
should be used to retrieve rows that match complex logical conditions
|
|
and regular expressions.
|
|
.SH "See Also"
|
|
.B
|
|
append,
|
|
column,
|
|
delete,
|
|
index,
|
|
replace,
|
|
row,
|
|
seek,
|
|
update
|
|
.R
|
|
.br
|
|
COHERENT Lexicon:
|
|
.B
|
|
egrep,
|
|
grep,
|
|
look,
|
|
time
|
|
.R
|