Efficient Lazy Loading of a Tree

By on January 27, 2010 9:36 am

Dojo 1.4 sports a fantastic tree widget, complete with ARIA compliance, keyboard accessibility, and internationalization (including right-to-left layout for appropriate countries and languages). For large tree data sets, we want to be able to only load the necessary data for the visible nodes of the tree. As a user expands a node, we then want to load the children of that node. Ideally, we only want to make one HTTP request per expansion for optimal performance. Historically, effective lazy loading has been a challenge, but some recent additions will make it much easier to utilize efficient lazy loading mechanisms in the tree.

The Dojo tree widget supports lazy loading, but it typically connects to a Dojo data store for all its data through a model-store adapter. Consequently, the tree itself does not define the actual data loading mechanism, as that is up to the store. The tree merely requests data from the store as needed. However, the JsonRestStore fully supports lazy loading with a well defined mechanism for retrieving deferred data from the server. When the JsonRestStore is used with the tree widget, it makes it possible to lazy load nodes in the tree as nodes are expanded. JsonRestStore supports lazy loading by using JSON referencing, whereby items can be referenced from other properties and arrays and the full item can later be retrieved when needed (with loadItem).

The model-store adapter now in Dojo 1.4 and later supports an option for a loading mechanism that facilitates single requests per node expansion. Previously (in 1.3), when a node was expanded the tree would request all the children and if any of the children had not been loaded, the tree would request that each child’s data item be fully loaded (this is done to ensure that each child has a label and information about whether or not it has children so the child nodes can be properly rendered) resulting in a request for each child of the expanded node, which is clearly inefficient. However, now when the model’s deferItemLoadingUntilExpand property is set to true, the tree will not attempt to load all of the children, but rather will only load the item for the expanded node if needed. This allows us to leverage the JsonRestStore’s support for partially loaded items. When a node is expanded and the item is loaded, the server can provide a JSON representation of the item which includes references to the children, and a partial set of properties for each child, which can include the label and children information for proper rendering. Each of these children can then be fully loaded when they are expanded (with their partial children objects). With this strategy, each node expansion will rely on only a single HTTP request.

Let’s take a look at how to build a lazy loaded tree with the JsonRestStore. We begin by creating a store:

myStore = new dojox.data.JsonRestStore({target:"tree/", labelAttribute:"name"});

Now, we will create the model adapter for the tree to access the store. This is where we use the new deferItemLoadingUntilExpand property:

myModel = new dijit.tree.ForestStoreModel({
	store: myStore,
	deferItemLoadingUntilExpand: true,
	query: "root",
	childrenAttrs: ["children"]
});

Next, we can create a tree:

myTree = new dijit.Tree({model: myModel}, treeNode);
myTree.startup();

Now, we can build our data that is supplied from the server. The first request that the JsonRestStore will make to the server will be a request for the top level nodes (the children of the root). The tree will make the initial request using the query provided to the model, and the JsonRestStore will combine that with the target. In this case, the request will be made to the path “tree/root”. Leveraging the partial loading support in JsonRestStore, we can serialize references to each of the items that will be children of the root node in the response, and only include the properties necessary to render these nodes (label and children info):

request:
GET /tree/root
response:
[ 
	{ $ref: 'node1', name:'node1', children:true},
	{ $ref: 'node2', name:'node2'},
]

This provides sufficient information to render the top level of the tree, as well as the link information for retrieving the full representation of each item. We don’t need to actually include the children, just the presence of a children property will indicate to the Tree that the node is expandable and an expansion icon will be included. Now when a user clicks on one of these nodes, the tree will ask the JsonRestStore to load the item and the JsonRestStore will request the resource for the URI specified by the $ref property. In this case, it will request node1. This URI is interpreted relative to the target URI of the store, so in this case, the JsonRestStore will request “tree/node1”. Your server can then respond:

request:
GET /tree/node1
response:
{ id: 'node1', name:'node1', someProperty:'somePropertyA', children:[
			{ $ref: 'node1.1', name: 'node1.1', children: true},
			{ $ref: 'node1.2', name: 'node1.2'}
]}

Here we see the full representation of node1. This not only includes the name, but may include additional properties that are used in other application logic. We also include an array that lists all the children of this item. Once again we use partial representations of these children to minimize the data transferred over the wire to the client. Whenever any of these children are expanded the process will be repeated and another request will be made to the server for the full representation of that child.

lazy-tree.png

The example code for lazy loaded trees is available in Dojo at /dijit/tests/Tree_with_JRS.html.

If you are updating data in the store, you should be aware of one more tip when using the Tree with the JsonRestStore. By default, the ForestStoreModel adapter will re-query the top nodes on every onNew notification event and every onDelete event that involves a top level item. This can result in queries to the server even though the server has not yet been sent all changes. This makes top level additions essentially disappear when the re-query takes place. You may need to override the _onNewItem and _onDeleteItem to provide your own logic about where new and deleted items should be placed in the hierarchy.

Another powerful feature of the referencing capabilities of JsonRestStore is that individual items can be referenced from multiple parent items. Consequently an item could exist in multiple places in the tree, under different parents.

Together, the Tree and the JsonRestStore provide a powerful combination for lazy loading data that allows for large extensive hierarchical data to be displayed without large upfront data transfers. The JsonRestStore’s partial loading support can be leveraged so that we can perform lazy loading with a single request per expansion.

Comments

  • Karl Tiedt

    Hey Kris, quick question on this… what if node1.1 was last used in an expanded state… is JRS capable of doing that in 1 query as well?

    IE: expanding node1 fetches nodes 1.1/1.2 AND because 1.1 was last stored in an expanded state is there a means to include 1.1->children data in that same 1 request so you get 1.1->1.1.x/1.1.y/1.1.z and 1.2?

  • @Karl: The JRS will interpret JSON objects with $ref as lazy, and those with ids as fully loaded objects, and the server’s response can include as many fully loaded objects as desired. I imagine it would be possible for the server to examine the Tree’s expansion cookies to determine which objects to provide a full version of and which to only include a partial version of. So JRS doesn’t provide any particular tool to send this information, but by virtue of the fact that the Tree uses cookies and the JRS can handle mixed full and partial objects, I think this would be possible.

  • Thanks for this article,
    Having done quite some work with the dijit tree it really sparked my interest. Based on my experience I consider the lazy loading method a slightly enhanced flavor of what was already available. Instead of sending the child information with the data item now an interim step is required to tell the tree/model if a data item has children. While testing several scenarios with my own tree implementation with multi state checkboxes I found that executing a forced data load (load the entire file at the start) dramatically improved the tree startup time, I’m talking 5-6 times faster. As a result I’m really wondering when would you use the lazy loading method especially considering the amount of data required to populate a tree is very small, its all text based and almost every HTTP server compresses anything they get their hands on anyway. If you take a look at my dijit tree demo page at http://www.thejekels.com/dojo/demo/checkboxtree it only take 2Kb to populate it.
    I would love to know some scenarios when you would recommend using the lazy loading method.
    Regards,
    Peter

  • Hi Peter
    Consider using the tree to display the servers file system with thousands of files and folders. Even if you are right, that this amount of data is not a problem to transfer fast, the time it would take to recursively parse the entire file system on the server, would take a long time. Especially when you have multiple users. With the lazy loading tree, only what you require at the moment, is queried on the server and then transmitted.

    Even of more interest is the situation, when you want to update, delete or create new tree items. Then the JsonRestStore with lazy loading is the best choice. It would make sense to completely refresh the entire tree every time you update, create or delete an item.

  • @Peter: If you are dealing with a smaller data set, loading the data up front certainly makes sense. Lazy loading is important for trees for which loading the entire data set up front could be prohibitively expensive (if there is no limit on the number of nodes that might need to be loaded).

  • Simon & Kris,
    Thanks for your response. I do agree that if you use a tree to display the content (directory structure) of a file system or if you need to make frequent updates lazy loading makes sense.
    Peter

  • Linus

    Thanks Kris Zyp… i was searching for lazyloading and i found this very useful… but i have a small problem… it happens that i have more than 200 to 300 leaf to be loaded in a single node… is it possible to use lazy loadin such that i can load the data as i scroll by in the menu…

  • I can use lazy loading in tree, but how do I add an item to an array of references? For instance, in schema below, how do I add a User to RolesSchema.Users ? Given schemas below, when I add User using parentInfo, the JsonRestStore/ServiceStore/Json.Rest get confused and think I’m adding a Role rather than User. Instead of a Put call with additional reference, a Post call is issued with the User properties, but to Role store. When I require dojox.json.schema, an exception is thrown because User object is validated against Role schema.

    var RolesSchema;
    var UsersSchema;

    UsersSchema = {
    id: “Users”,
    properties: {
    Id: { type: “number” },
    Name: { type: “string” },
    Login: { type: “string” },
    OrganizationUnits: { items: { type: “object”} },
    Roles: { items: RolesSchema }
    }
    };
    RolesSchema = {
    id: “Roles”,
    properties: {
    Id: { type: “number” },
    Name: { type: “string” },
    Authorizations: { items: { type: “object”} },
    Users: { type: “array”,
    items: { type: “object”,
    properties: UsersSchema.properties
    }
    }
    }
    };

  • Pingback: Creating a dojo.store.JsonRest backend server using ZendFramework (PHP) | Respondify Blog()

  • dongguangming

    I think it useful for me.

  • suresh

    As i am beginner it is very useful for me thanks :)