Indeksy prawie jak w bazie danych

Spotkałem się ostatnio z ciekawym problemem dotyczącym wyszukiwania danych. Zlecenie na program zaliczeniowy było proste napisać bibliotekę, ale bez użycia RDBMS. zabawa opiera się więc o kolekcje i ich odpowiednie projektowanie. Zadanie stosunkowo proste do momentu, w którym nie trzeba wyszukiwać danych po którejś z „kolumn”. W tym momencie mamy dwie drogi.

  • Ręczne iterowanie się po kolekcji i wyszukiwanie po id przez porównanie z każdym obiektem.
  • Emulowanie indeksu z RDBMS

Pierwsza metoda jest mało wydajna. Ma złożoność liniową, a przecież da się szybciej. Poza tym drugie rozwiązanie jest znacznie ciekawsze.

Krok 1. Klasa Autor

public class Author {
private int id;
private String name;

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getId() {
return id;
}

public Author(int id, String name) {
super();
this.id = id;
this.name = name;
}

}

Krok 2. Po czym indeksujemy

Załóżmy, że chcemy indeksować po polu name. W sumie indeks dobry jak każdy inny.

Krok 3. „Tabela” authors

Zdefiniujmy klasę która będzie emulowała tabelę authors:

public class Authors extends LinkedList {

private static final long serialVersionUID = 1L;
}

Nie bawimy się w jakieś rozczulania czy kombinowanie tylko rozszerzamy LinkedList. W ten sposób mamy do dyspozycji odpowiednie metody i za darmo kontrolę typu.

Krok 4. „Indeks” na tabeli authors z pola name

Tu też nie ma się co bawić i rozczulać:

public class AuthorsNameIndex extends HashMap{

private static final long serialVersionUID = 1L;

}

I tu pierwsza pułapka. Pojawia man się poważna redundancja danych. Tabela authors i indeks przechowują wszystkich autorów. Nie jest to dobre rozwiązanie. Jednak nie będę go zmieniał ponieważ oznaczałoby to zmianę klasy Authors i w konsekwencji Author. Zmiana ta polegała by na ekstrakcji pola id jako klucza do map. Na razie olać.

Pytanie 1. Co robi programista?

Mamy już „Bazę danych”, która ma nawet „Indeks” w czym zatem problem? Przyjrzymy się takiemu oto kodowi:

Authors authors = new Authors();
authors.add(new Author(0, "a"));
authors.add(new Author(1, "b"));

Widać w czym problem? Dla mało spostrzegawczych nie ma możliwości dodawania autorów do indeksu tak by obiekt dodany do tabeli i obiekt dodany do indeksu był to ten sam obiekt. Musimy zatem nadpisać metodę add() dla klasy Authors.
Nowa klasa wygląda tak:

public class Authors extends LinkedList {

private static final long serialVersionUID = 1L;

private static AuthorsNameIndex authorsNameIndex = new AuthorsNameIndex();

@Override
public boolean add(Author o) {
boolean b = super.add(o);
authorsNameIndex.put(o.getName(), o);
return b;
}

public Author get(String name) {
return authorsNameIndex.get(name);
}

}

Klasa została wzbogacona o indeks i metodę wybierającą na podstawie danych z indeksu.

Teraz wystarczy napisać testy i bangla 🙂

2 myśli na temat “Indeksy prawie jak w bazie danych

  1. Czegoś tu nie rozumiem: po co nam klasa AuthorsNameIndex? Na złość Occamowi? 😉

    IMHO, o ile istnienie klasy Authors jest jeszcze jako tako uzasadnione, o tyle AuthorsNameIndex już nie.

  2. Klasa ma za zadanie stworzenie reprezentowanie indeksu na tabeli. Jednak przedstawione rozwiązanie jest tylko bardzo okrojonym przykładem. W rzeczywistości dodanie indeksu (indeksów) powinno być niewidoczne dla programisty. Na chwilę obecną nie mam czasu o tym myśleć, są inne ważniejsze problemy.

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax