Why use B-Tree?

A well balanced B-Tree has several advantages over a Hashtable

1. Faster to insert a new item
2. It is fast and easy to search for ‘Nearest Hit’ items. This is very important in building a search dictionary. Searches can be done with partial string, for example to search for the word ‘where’, we can start with the string ‘whe’.

Once the first “Nearest Hit” node is obtained, it is easy to walk through the B-Tree list to obtain the matching nodes.

Design

The indexer consists of a set of B-Trees (Word Dictionary and MAP tables) and a collection of ‘observers’ looking for ‘user input’, ‘file changes’ and ‘system idle time’ to update or query the B-Trees.  Each observer runs in separate threads.

1. ‘User Input’ observer reads user’s input and queries the indexer for matches
2. ‘File Change’ observer waits for file change notifications from the observed directories and queue the change information in a list.
3. ‘System Idle Time’ observer wakes up when the system is idling and process the queued file change information. This observer is responsible for indexing modified files.

File Change Observer

            This observer opens the directory names specified in the ‘settings.ini’ file (located in the same folder as ‘INDEXER.EXE’). Later it creates an IoCompletionPort and waits for file changes. ‘IoCompletionPort’ allows a single thread to observe several directories at the same time. It uses ‘ReadDirectoryChangesW’ API to retrieve the file changes from the system whenever a IoCompletionPort reports a completion status. All the new, modified or deleted files names are put in a file name list.

             Class Name: CFileObserver  (filechg.h and filechg.cpp)

System Idle Observer

                   This observer sleeps most of the time and whenever it wakes up it uses the ‘NtQuerySystemInformation’ API exposed by NTDLL.LL to calculate the CPU usage. If the CPU usage is less than 5% and there are file names in the file name list (queued up by the File Change Observer), it will de-queue the file names will parse and index the content of the files.

            Class Name: CIdleObserver  (observer.h and observer.cpp)

User Input Observer

            This observer waits for user inputs on ‘STDIN’ and queries the indexer to retrieve file names containing the input string. It runs in the main application thread and will continue to run until user presses CTRL+C.

             Class Name: CInputObserver  (observer.h and observer.cpp)

The Indexer

            This class indexes the file content. It uses the dictionary lookup algorithm to index and search words. There is only ONE dictionary in the sample code provided. If you need high performance lookup, you should create an array of dictionaries based on the hash value of a portion of the word (say, the first three characters of the word). In such a case the dictionary is a Hashtable of B-Trees and should provide fast lookups. See below for the schema design of the indexer.

1. Dictionary (m_dict of CIndexer class)

            This table maps words to its address. An address is 64bit integer. Every query will lookup the address of the word from this table and later uses the address for all other table lookups.

Word1	Address1
Word2	Address2
Word3	Address3

2. File Map Table (m_file of CIndexer class)