Image B-TREE Definitions by Stan Sieler Definitions: "B-Tree search" ... is some kind of search that involves the attached B-Tree, instead of a simple hash (and look only for the single matching entry) "trailing-@ search" ... is a B-Tree search where only the leftmost "n" characters of each key are compared to the DBFIND argument. Thus, for MPE's LISTF command, "cat@" is a trailing-@ search, but "cat@dog" is not. "wildcard character" ... generally refers to "@" (and not to "?" or "#" in MPE's terms), and is the character that means "matches all trailing characters". "complex argument" ... a DBFIND argument that is a record structure, containing search control information as well as key data. (Used in DBFIND modes 4 and 24.) The modes of DBFIND supported are: 1 .. If BTREEMODE1 is on, and the key type is X or U, do a B-Tree DBFIND if the argument contains wildcard characters (e.g.: "S@"), otherwise a non-B-Tree DBFIND. For B-Tree finds, the argument is scanned for the first occurance of the wildcard character, and a "trailing-at" search is done. Subsequent text in the key value is ignored. For B-Tree finds, the chaincount is accurate, and status halfwords 7-8 and 9-10 record the last entry in the last chain, and the first entry in the first chain of the super-chain. 4 .. Do a B-tree find, with accurate chain counts. NOTE: the argument is in complex-format (defined below). 10 .. do a non-B-Tree only DBFIND mode 1 equivalent. 21 .. same as mode 1, above, but the chain count is not accurate. (This is a high-speed version of mode 1.) Status halfwords 7-8 and 9-10 will have 2^31-1. The chain count is set to $7fffffff, and the forward/backward pointers are set to unknown values. 24 .. same as mode 4, above, but the chain count is not accurate. (This is a high-speed version of mode 4.) Status halfwords 7-8 and 9-10 will have 2^31-1. NOTE: the argument is in complex-format (defined below). The chain count is set to $7fffffff, and the forward/backward pointers are set to unknown values. DBFIND mode summary chart (see footnotes for explanations), for details with a path to a master data set that has a B-Tree: | | Accurate | DBFIND mode | B-Tree search? | Chain counts? | "argument" style ------------|-----------------|----------------|------------------ | | | 1 | maybe (#8) | YES (#1) | mode 1 (#10) | (#9) | (#2) | | | | 4 (#6) | YES | YES (#2) | mode 4 (#5) | | | 10 | NO | YES (#1) | mode 1 (#10) | | | 21 | YES (#9) | NO (#3) | mode 1 (#4) | | | 24 (#7) | YES | NO (#3) | mode 4 (#5) Footnotes: #1 the chain count will be the number of entries in the single chain located. (As in DBFIND mode 1 today) #2 the chain count will be the sum of all chain counts (i.e., the number of entries in the super-chain) #3 2, 147,483,647 (2^31-1) will be returned as the chain count. #4 IMAGE B-Trees (and TPI products) treat the argument just like a DBFIND mode 1 style argument. #5 see "DBFIND mode 4 argument syntax" description, below. #6 Mode 4 is a new mode, no TPI product currently uses this mode. Its high-speed counterpart is mode 24, which doesn't return an accurate chain count. Modes 4 and 24 are currently unused by any TPI product. #7 Mode 24 is a new mode, no TPI product currently uses this mode. Since mode 24 does not return an accurate chain count, it is a higher performance version of mode 4. #8 If the root file flag BTREEMODE1 is ON, then a DBFIND mode 1 will be treated as a B-Tree search, with mode-1 style argument. If the root file flag BTREEMODE1 is OFF, then a DBFIND mode 1 will not be treated as a B-Tree search, even if the data set has a B-Tree. #9 For key items that are text types (U, X), a B-Tree search will be done. If the key item is a non-text item (i.e., not type X or U), then a B-Tree find will not be done, and a normal non-B-Tree find (mode 1 with BTREEMODE1=OFF) will be done instead. A programmer can do a B-Tree find with non-text items by explicitly using DBFIND modes 4 or 24. (See "DBFIND mode 1-style and non-text keys" below.) Note: this mode is similar to current TPI mode 21. #10 When doing a B-Tree find, mode-1-style arguments are scanned to find the *first* occurance of the current wildcard character in the argument text. If the wildcard is not found, a non-B-Tree search is done (even if the DBFIND mode was 21). If the wildcard is found, the rest of the argument text is ignored. NOTE: this does *not* match the functionality of "@" in, say, the MPE LISTF command (e.g., LISTF cat@dog is not the same as LISTF cat@), but does match the functionality of current TPI implementations. If the wildcard character is found at character k+1 (1-based), then the returned super-chain will consist of all keys that match the argument in character positions 1..k. When not doing a B-Tree find (i.e., mode=1 and BTREEMODE1=OFF, or more = 10), the entire argument, including any wildcard characters, will be treated as the actual argument as is done today for a DBFIND mode 1 (on a non-TPI data set). Note: the length of the argument may not exceed the item length. DBFIND Argument --------------- The "complex-argument" for DBFIND modes 4 and 24: argument: (for DBFIND mode 4 (and mode 24)) Bytes Meaning ----- -------------------------------- 0, 1 Type of generic search. An ASCII character pair is in this field: "< " search for key values LESS than argument1 "<=" search for key values LEQ argument1 "= " search for key values EQL argument1 (i.e., similar to a DBFIND mode 1) ">=" search for key values GEQ argument1 "> " search for key values GTR argument1 "[]" search for key values GEQ argument1 AND LEQ argument2 "@c" wildcard search: scan argument for the first wildcard character. (Call that character position k, 1-based), Search for keys that match first k-1 characters of argument. "c": if non-blank and non-null, then it is the wildcard character that will be used. E.g., a Unix-shell-like "*" would be specified as: "@*". The standard MPE "@" would be "@@". If "c" is a blank or null, then the current default wildcard (stored in the root file) is used. The wildcard character is changable via DBUTIL's SET BTREEMODE1=ON [,WILDCARD=c] command. 2, 3 version # (must be 0) 4, 5 The size (in bytes) of argument1 (not including these two bytes). 6, 7 The size (in bytes) of argument2 (not including these two bytes). 8...8+n-1 "Argument1" The n bytes of argument data (e.g., for an X10 field, n = 10) (the following two fields exist only for range searches ("[]", and "()") 8+n..8+n+m-1 "Argument2" The m bytes of the second argument's data. (e.g., for an X10 field, m = 10) ("n" must match "m" for now) A Pascal/iX view of the above is: type dbfind_arg_type = $alignment 2$ record dbf_type : pac2; {e.g., "<="} {0 @ 2} dbf_version : shortint; {must be 0} {2 @ 2} dbf_arg1_bytes : shortint; {4 @ 2} dbf_arg2_bytes : shortint; {6 @ 2} {NOTE: arg1 data is variable sized...2 to 256 bytes} { and, arg2 data might not even be present. } { Still, the following serve to define a record} { that can hold the worst case arg1 & arg2... } dbf_arg1_data : packed array [1..256] of {8 @ x} char; {*REAL* dbf_arg1_data is variable sized} {*REAL* dbf_arg2_data is variable sized} spare_area : packed array [1..256] of {8 @ x} char; {if present, arg2 data starts at record + 8 + arg1_bytes} end; {8 + 256 + 256} NOTE: the above implies that the only type of wildcard searching in phase 1 is "trailing-@" searching! ("> ", ">=", "[]" are not wildcard searches.) -- Stan Sieler sieler@allegro.com http://www.allegro.com/sieler.html