I need LH table index lookup functionality in a web interface. I asked yesterday on the common list if somebody had source to share, but haven't received any reply yet. I might want to use the same code later in a non-web setting, but my current concern is index lookup from a web interface.

I also want/need to know more about the structure of index tables, especially if I have to write code from scratch. I know a little bit from before, and I learn some from just studying the rows of index tables, but there are details I need to be 100% sure about. My clients' indexes can grow to be very large, especially the cross ref ones. Some values may have more then 64K of keys, so I have to know how that is handled. Is there any documentation on the structure of index tables around? I cannot seem to find any on this site - neither for Arev nor OI.

So what kind of functionality am I looking for? I want the user to be able to browse forwards or backwards from a certain point (value) in the index, listing either values alone, or values with keys, or values with number of hits.

I also want to give the user wildcard or pattern matching functionality, e.g to list all values containing a certain substring. This of course means I have to traverse the whole index sequentially and filter out the matching values.

The web-accessible database will be fairly static. I think we can assume it's separate from the production database and batch updated (or replaced) once a day or once a week. So I've toyed with the idea of having a more accessible version of the indexes and do the index lookup on that. But I still need to traverse the whole index sequentially once - to make that more accessible version.

Any help appreciated… …or else!

- Oystein -

Oystein,

Have you looked at the INDEXLOOKUP source in OpenInsight?

Cameron Purdy

Revelation Software

Oystein-

For the record, I did reply to your message on the board.

I will not be ignored!!!!

Mike Ruane

WinWin Solutions Inc.

WWW.WinWinSol.com

Oystein -

Take a look at the source code to the INDEXLOOKUP prodcedure. Choose FILE | OPEN STORED PROCEDURE, then open the procedure INDEXLOOKUP.

As for the structure of index tables, let me get back to you on that.

- Chris

Revelation Software

Mike,

I'm confused. I cannot remember that reply and browsing again now I cannot find it either. Would you mind re-posting it here?

But I did notice a reply of yours to Greg (?) where you mentioned Btree.Read. (His question was about something else but I might be interested in anything that has to do with index access.) I'll check out Btree.Read now. (Must confess it took a while before I managed to locate the docs; they were in "Using BTREE.READ (TB#101)" in the Knowledge Base - Arev Dept.)

- Oystein -

Chris/Cameron/Mike,

I have studied IndexLookup already. It uses Collect.IXVals, and Collect.IXVals is no good. It does too much work - tries to get *all* the index values. And it cannot handle sets of values ] 64K.

I need something more low-level, and I might have found what I need in the "Using BTREE.READ" article in the Knowledge Base - Arev (TB#101). The article has an example where BTREE.READ is used to find the right starting point in the index (the row that contains a certain value), and ReadMat to read more rows.

(Btw - there are a couple of errors in that example, one of them serious (the index variable "i" is not updated).)

Thanks to you Mike who made me aware of Btree.Read (in a reply to somebody else, but who cares ).

I'm still in the market for data on the index structure, but just now I have only one question: Are fields 2 and 3 forward and backward pointers for a strict linear chain through the index? I need to go forward and backward in the index, and so far I have thought I had to traverse a tree structure. (Deja vu? Have I been through this before? I think somebody (Cameron?) once told me about this. But I never used the knowledge at that time, and finding that old posting now is like searching for a needle in a haystack.)

- Oystein -

I said I had only one question, but that wasn't true of course. (Am I related to that elephant's child or not?) But instead of bothering you with other questions now I'll just sit tight and wait for that documentation of the index structure I hope Chris or somebody else will dig up for me.

- Oystein -

Øystein Reigem, Humanities Information Technologies, Allégt 27, N-5007 Bergen, Norway. Tel: +47 55 58 32 42. Fax: +47 55 58 94 70. E-mail: oystein.reigem@hit.uib.no. Home tel/fax: +47 56 14 06 11.

Oystein -

I am going to be doing some research into the structure of index files. Hopefully I will have some information by the end of the week.

I will let you know what I find out.

-Chris

Revelation Software

Chris,

Great!

With what I know already I can write a preliminar version of an index accessing function, that works well enough for me to proceed with the web interface stuff.

- Oystein -

<code>

function Collect.IXVals(FileName, FieldName, List)

******************************************************************************
*
* This program is proprietary and is not to be used by or disclosed
* to others, nor is it to be copied without written permission from
* Revelation Technologies, Inc.
*
* Product    :  OpenInsight
* Client     :  RTI
* Version    :  3.1
*
* Description:  This function performs an index extraction on 
*               the specified indexed column.
*
* History    :  (date, initials, notes)
*   04/19/88  acj  Added standard top
*   04/19/88  acj  BetaBug 955
*   03/01/90  Pat  Rep with BTREE.UTIL routine, fix prob 2031
*   11/21/90  Pat  Softcode B296
*   02/09/93  abh  Account for old names in lookup
*   12/22/95  cp   Reworked, removing Arev stuff
*
******************************************************************************

declare function   Index.Open, Test_Abort
declare subroutine BTree.Util, Set_Status

$insert Rev_BP, SysCommon
$insert Rev_BP, BTree_Equates
$insert Rev_BP, FSErrors_Hdr
$insert Rev_BP, FSErrors_200
$insert Rev_BP, Logical
$insert Rev_BP, Status_Equates

equ SI_INDEX_PREFIX$  to "!"
equ MAXLEN$           to 64000


  dim Array(ID.IX$)

  List="

  if Index.Open(SI_INDEX_PREFIX$: FileName, f_Index) else
    Set_Status(SETSTAT_ERR$, FS_PREFIX$: FS_INDEX_OPEN_ERR$, SI_INDEX_PREFIX$: FileName)
    return
  end

  RealName=FieldName
  convert @lower.case to @upper.case in RealName
  read Test from f_Index, RealName then
   * clear whatever we read
    Test="
  end else
   * if the name didn't exist, perhaps the index was changed.
    if RealName -5,5=.XREF" then
      RealName -5,1=_"
    end
  end

  BTree.Util(1, RealName, f_Index, Root, "", mat Array, Code, Status)
  if Code # "ESC" then
    BTree.Util(3, RealName, f_Index, Root, Key, mat Array, Code, Status)
    if Status then
      gosub Extract
    end
  end

  List -1,1="
  BTree.Util(2, RealName, f_Index, Root, "", mat Array, Code, Status)
  convert @vm to @fm in List

return List


**********************
* extract index values
**********************

Extract:
  loop
    if Test_Abort() then
      List="
      return
    end

    matread Array from f_Index, Key else
      Set_Status(SETSTAT_ERR$, FS_PREFIX$: FS_INDEX_CORRUPT_ERR$, FileName: @fm: RealName)
      return
    end

    Chunk  =Array(VALUE.IX$)
    if len(List) + len(Chunk) ] MAXLEN$ then
      List := "***LIST TRUNCATED***": @vm
      Set_Status(SETSTAT_ERR$, FS_PREFIX$: FS_LIST_OVERFLOW_ERR$, "")
      return
    end

    if index(Chunk, @vm, 1) then
      List := Chunk: @vm
    end else
     * only one value - may be part of a split leaf
      locate Chunk in List using @vm setting Pos else
        List := Chunk: @vm
      end
    end

    Key=Array(NEXT.LEAF.IX$)
  while Key
  repeat
return

</code>

Cameron,

I had assumed the data I want to get at - the core index data, i.e values and keys - are to be found in a linear sequence of leaf nodes, and that the other nodes constitute a hierarchy on top of that. The Collect.IXVals source seems to confirm that. I don't want to sound ungrateful, but apart from that I couldn't find much of value.

The Collect.IXVals source introduces the undocced (?) BTree.Util function, which it uses to find a starting point, but I assume I can make do with Btree.Read.

It still would be nice to have some documentation of the upper levels of the hierarchy, but I think I can manage with what I have.

Thanks.

- Oystein -

Oystein,

The following are doc'd:

RLIST

COLLECT.IXVALS

BTREE.EXTRACT

Basically, the original desire was to make indexes transparent to the user. Even though I have worked extensively with Arev and OI (both here and as an app developer before that) I don't have any experience with even BTREE.EXTRACT, so either (a) I was clueless or (b) the available utilities and commands were enough for what I needed. (The application I worked on was on the order of 500 screens, so it was not small.)

That said, I know that the BTREE index support is much more powerful than what is exposed and I have listened to developers rave about what they have been able to use it for. I happened to know COLLECT.IXVALS because I had to clean it up a while back … so I thought it would be helpful in your quest. If I knew more, I'd post it, trust me.

Your best bet for detailed answers is probably Aaron Kaplan … he has worked a bit with BTREE index code.

BOL

Cameron Purdy

Revelation Software

Cameron,

Thanks. The Btree.Read article does mention other nodes than leaf nodes (nodes that "contain branch information") but the confusing thing is it says those nodes are leaf nodes too… Nevermind. I think I'll gamble on having got it right now, and if I seem to get faulty results later when I do more thorough testing I'll try to get hold of Aaron then. Thanks again.

- Oystein -

View this thread on the Works forum...