Indexing

saoj — GMT

When your collection becomes too big, even in-memory searches can become expensive. Imagine a Java collection with 1 million users and you need to find all users with the last name equals to "Smith". Iterating through all elements is clearly not an option. What you need is INDEXES.

Space4J supports 4 different types of indexes through maps, in other words, when you create an index a new Java Map is created to store the index.

The four types of index are:

:arrow: Index.TYPE.REGULAR = Unique index non-sorted. This is used to get an user by its id for example, where each user has an unique id.
[code]
User u = usersById.get(2345);
[/code]

:arrow: Index.TYPE.SORTED = Unique index sorted. This is used to get a list of users in a range of ids (ex: 4000 < id < 5000). Also used when you need to fetch users sorted by the indexed field.
[code]
Map map = usersById.subMap(4000, 5000);
[/code]

:arrow: Index.TYPE.MULTI = Non-unique index non-sorted. This is used to get all users with age equal to 23.
[code]
Collection coll = (Collection) usersByAge.get(23);
[/code]

:arrow: Index.TYPE.MULT_SORTED = Non-unique index sorted. This is used to get all users with age >= 23 and age <= 40. Also used when you need to fech users sorted by the indexed field.
[code]
Map> map = usersByAge.subMap(23, 40);
[/code]

The [url="http://www.space4j.org/phonebookindex.jsp"]PhoneBookIndexing.java[/url] program provides examples of how to create and user indexes for your collections in memory. Below is the source code:
[code]
package org.space4j.examples.phonebook;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentNavigableMap;

import org.space4j.Space4J;
import org.space4j.implementation.SimpleSpace4J;
import org.space4j.indexing.Index;
import org.space4j.indexing.IndexManager;
import org.space4j.indexing.Key;
import org.space4j.indexing.MultiMap;
import org.space4j.indexing.MultiSortedMap;

public class PhoneBookIndexing extends PhoneBook {

private static final String INDX_LASTNAME = "indx_lastname";

private static final String INDX_AGE = "indx_age";

private final Index indexByLastName;

private final Index indexByAge;

public PhoneBookIndexing(Space4J space4j) throws Exception {

super(space4j);

IndexManager im = space.getIndexManager();

// If index does not exist, let's create it...
if (!im.checkIndex(INDX_LASTNAME)) {

/*
* Index name = INDX_LASTNAME
* Map in the Space that will be indexed = MAP_NAME
* Type of index = MULTI = non-unique index
* Object that will be indexed = User.class
* Atributes of the object that will be indexed = "lastName"
*
* We want to create this index because we will be searching
* for Users by lastName. We don't want to do a full table
* scan anymore like in the example without indexes.
*/

Index indx = new Index(INDX_LASTNAME, MAP_NAME, Index.TYPE.MULTI,
User.class, "lastName");

boolean ok = im.createIndex(indx, space4j);

if (ok) {

System.out.println(indx + " created!");

} else {

System.out.println(indx + " could not be created!");
}
}

// If index does not exist, let's create it...
if (!im.checkIndex(INDX_AGE)) {

/*
* Index name = INDX_AGE
* Map in the Space that will be indexed = MAP_NAME
* Type of index = MULTI = non-unique sorted index
* Object that will be indexed = User.class
* Atributes of the object that will be indexed = "age"
*
* We want to create this index because we will be searching
* for Users by age. The index will be SORTED because we want
* to search for users in a age range. (age > min and age < max)
*/

Index indx = new Index(INDX_AGE, MAP_NAME, Index.TYPE.MULTI_SORTED,
User.class, "age");

boolean ok = im.createIndex(indx, space4j);

if (ok) {

System.out.println(indx + " created!");

} else {

System.out.println(indx + " could not be created!");
}
}

indexByLastName = im.getIndex(INDX_LASTNAME);
indexByAge = im.getIndex(INDX_AGE);
}

/*
* Let's override our search method to use our
* index instead of doing a full table scan.
*/
@Override
public Collection findUsers(String last) {

// Remember that our index is of the type MULTI.
// That's why we are doing this cast here.

MultiMap map = (MultiMap) indexByLastName.getMap();

// A multi-map will store a Collection for each key.
// That's why our index is NON-UNIQUE meaning the same
// key can be associated with many entries in the map.
// That makes sense as some users can have the same
// last name.

Collection coll = (Collection) map.get(last);

return coll;
}

@Override
public Collection findUsers(int minAge, int maxAge) {

// Remember that our index is of the type MULTI_SORTED.
// That's why we are doing this cast here.

MultiSortedMap map = (MultiSortedMap) indexByAge.getMap();

// A multi-sorted-map will store a Map for each key.
// That's why our index is NON-UNIQUE meaning the same
// key can be associated with many entries in the map.
// The map is also sorted by its key, meaning we can
// perform range searches efficiently.

ConcurrentNavigableMap subMap = map.subMap(new Key(minAge), true, new Key(maxAge), true);

Collection users = new ArrayList(subMap.size() * 3);

Iterator iter = subMap.values().iterator();

while(iter.hasNext()) {

// our collection here is actually a ConcurrentHashMap!

Map m = (Map) iter.next();

// this is not good as we are transversing the whole list twice!
// TODO: Create custom iterator for MultiSortedMap to avoid this?

Iterator iter2 = m.keySet().iterator();

while(iter2.hasNext()) {

users.add(iter2.next());
}
}

return users;
}

public static void main(String[] args) throws Exception {

PhoneBookIndexing book = new PhoneBookIndexing(
new SimpleSpace4J("PhoneBook"));

run(book);

}
}
[/code]

Latest posts for the topic "Indexing"

Indexing