Tips and tricks for Windows 8 JavaScript developer: creating a local full text search index - Eternal Coding - HTML5 / JavaScript / 3D development - Site Home - MSDN Blogs

Tips and tricks for Windows 8 JavaScript developer: creating a local full text search index


Tips and tricks for Windows 8 JavaScript developer: creating a local full text search index

  • Comments 3

One issue I have with UrzaGatherer is related to the search. As you may know, I have a huge list of cards saved locally and my application allows the user to search specific cards using a part of their name. But browsing more than 20 000 cards using a text search can be really expensive mainly on low-end hardware.

Currently the code looks like something like that:

cards = UrzaGatherer.CardsList.createFiltered(queryFunction)


I use the WinJS.Binding.List object to create a filtered view using my search pattern.

The filter function uses a simple indexOf function:

var queryFunction = function (card) {
    if ( !== -1) {
        return true;

    return false;


But obviously, it can take ages to perform a search using this solution. The complexity is almost O(n * m) which can be simplified to O(n²) (where n is the number of cards and m the average length of cards name).

So the question is: How can I optimize my search?

Building a full text search tree

One solution can be found with a search tree. This kind of structure allows you to perform a search with a complexity of O(n) where n is the average length of a card’s name.

You have to build the tree by feeding it with the strings you want to search. For each string, the tree will generate a branch with all the characters then a branch with n-1 character (starting after the first one) and so on.

For example, if we use the “urza” string the tree will look like that:



The leafs contain the id of the associated card.

If I add a new string like “Pizza” to my previous tree the resulting tree is:



Please note that some leafs can contain many cards (like for “ZA” and “A”)

The related code is pretty simple:

var root;

var processString = function(string, offset, node, object) {
    if (!string || offset == string.length) {

    var currentNode = node;

    for (var index = offset; index < string.length; index++) {
        var c = string[index];

        if (currentNode[c] === undefined) {
            currentNode[c] = {};

        currentNode = currentNode[c];

    if (currentNode.ref == undefined)
        currentNode.ref = [];

    if (currentNode.ref.indexOf( == -1) {

    processString(string, offset + 1, root, object);

var addString = function (string, object) {
    if (!string)
    if (!root)
        root = { };

    processString(string.toLowerCase(), 0, root, object);

Searching using the full text search tree

The search function is then a simple tree traversal:

var concatArray = function (source, data) {
    for (var index = 0; index < data.length; index++) {
        source[data[index]] = {};

var gatherResults = function (node, results) {
    for (var prop in node) {
        if (prop == "ref")
            concatArray(results, node[prop]);
            gatherResults(node[prop], results);

var searchString = function (string) {
    var currentNode = root;

    for (var index = 0; index < string.length; index++) {
        var c = string[index];

        if (currentNode[c] === undefined)
            return {};

        currentNode = currentNode[c];

    var results = {};
    gatherResults(currentNode, results);

    return results;

When the searched string is completely found, the algorithm gathers all the children leafs to produce the final result.

You can also persist your tree easily with JSON:

var persistIndex = function(filename) {
    var data = JSON.stringify(root);
    return Windows.Storage.ApplicationData.current.localFolder.createFileAsync(filename, 
Windows.Storage.CreationCollisionOption.replaceExisting) .then(
function (file) { return Windows.Storage.FileIO.writeTextAsync(file, data);
}); }; var resetIndex = function() { root = undefined; }; var loadIndex = function(filename) { return Windows.ApplicationModel.Package.current.installedLocation.getFolderAsync("data")
function(localFolder) { return localFolder.getFileAsync(filename).then(function(file) { return Windows.Storage.FileIO.readTextAsync(file).then(function(data) { if (data) { root = JSON.parse(data); } }); }); }); };

For instance, the complete index for my 20 000 cards weights 6 Mb.



Blazing fast !! Nothing more Sourire. Using my search tree I can search through the entire collection in less than 300ms where before it can take up to 20s for the same result.

But beware: this optimization is costly in terms of memory consumption (due to the index).

At the end of the day, it is a good tool for you if you want to search your data without using a backend server (or when you are offline).

Leave a Comment
  • Please add 3 and 8 and type the answer here:
  • Post
  • David,

    Have you considered using a light DB engine like SQLite ?


  • It is a good option too but in my case I only need a search index (my data is produced and save using json)

  • Thanks for share

Page 1 of 1 (3 items)