|
|
|
Below we will demonstrate how to index your objects so that you can do faster searches instead of having to iterate through all your objects in your list to find what you want. If you have a small list of objects, using an index will not make any difference. However, as your list grows, using an index becomes mandatory to avoid very slow search times.
We want to do two searches: search users by a last name and search users in a given age range. For the first search we will use a MULTI index, which is a non-unique index. This will make it easier and faster to fetch all users with a given last name. For the second search we will use a MULTI_SORTED index, which is a non-unique sorted index. The reason we need a sorted index for the second search is because we want to fetch a submap of all users >= minAge and <= maxAge.
If we were searching on an unique field, such as ID, we could have used the REGULAR and SORTED indexes instead.
The complete source code for the PhoneBook application with indexes can be downloaded here: PhoneBookIndexing.java. Make sure the space4j.jar is in your classpath before compiling and executing.
package org.space4j.examples.phonebook;
// imports here...
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<Object> 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<Object> coll = (Collection<Object>) map.get(last);
return coll;
}
@Override
public Collection<Object> 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<Key, Object> subMap = map.subMap(new Key(minAge), true, new Key(maxAge), true);
Collection<Object> users = new ArrayList<Object>(subMap.size() * 3);
Iterator<Object> iter = subMap.values().iterator();
while(iter.hasNext()) {
// our collection here is actually a ConcurrentHashMap!
Map<Object, Boolean> m = (Map<Object, Boolean>) iter.next();
// this is not good as we are transversing the whole list twice!
// TODO: Create custom iterator for MultiSortedMap to avoid this?
Iterator<Object> 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);
}
}