Hvilke datastruktur til at implementere en SQL, LIKE% søgning

Jeg har nu følgende:


import java.util.Enumeration;
import java.util.Hashtable;

public class PartialSearcher {
    Hashtable hash;
    String[] sortedArray;
    /**
    * @param args
    */
    public static void main(String args[]){
    Hashtable h = new Hashtable();
    h.put("hello", new Integer(1));
    h.put("hell", new Integer(2));
    h.put("alpha", new Integer(3));
    h.put("bye", new Integer(4));
    h.put("hello2", new Integer(5));
    h.put("solly", new Integer(6));
    h.put("sally", new Integer(7));
    h.put("silly", new Integer(8));
    h.put("zorro", new Integer(9));
    h.put("hi", new Integer(10));
    PartialSearcher p = new PartialSearcher(h);
    String args1 = "h";
    Object[] objs = p.match(args1);
    for(int i = 0; i < objs.length; i++)
        System.out.println(objs[i]);
    }
//    if(args.length == 0){
//        System.out.println("Usage: Search string missing.");
//        return;
//    }
//    else{
//        Object[] objs = p.match(args[0]);
//        for(int i = 0; i < objs.length; i++)
//        System.out.println(objs[i]);
//    }
//    }

    public PartialSearcher(Hashtable h){
    hash = h;
    createSortedArray();
    }

    public Object[] match(String s){
    int startIdx = binarySearch(sortedArray, s, 0, sortedArray.length-1);
    int endIdx = binarySearch(sortedArray, s+ '\uFFFF', 0, sortedArray.length-1);
    Object[] objs = new Object[endIdx-startIdx];
    for (int i = startIdx ; i < endIdx; i++)
        objs[i-startIdx] = sortedArray[i];
    return objs;
    }

    public void createSortedArray(){
    sortedArray = new String[hash.size()];
    Enumeration e = hash.keys();
    for(int i = 0; e.hasMoreElements(); i++)
        sortedArray[i] = (String)e.nextElement();
    quicksort(sortedArray, 0, sortedArray.length-1);
    }
    /**
    *
    * Takes on average O(Log N). Requires sorted data.
    */
    public static int binarySearch(String[] arr, String elem, int fromIndex, int toIndex){
    int mid,cmp;
    while (fromIndex <= toIndex){
        mid =(fromIndex + toIndex)/2;
        if((cmp = arr[mid].compareTo(elem)) < 0)
        fromIndex = mid + 1;
        else if(cmp > 0)
        toIndex = mid - 1;
        else
        return mid;
    }
    return fromIndex;
    }
    /**
    * Take on average O(N log N). Worst case is O(N^2)
    *
    *
    */
    public void quicksort(String[] arr, int lo, int hi){
    if(lo >= hi)
        return;
    int mid = (lo + hi) / 2;
    String tmp;
    String middle = arr[mid];
    if(arr[lo].compareTo(middle) > 0){
        arr[mid] = arr[lo];
        arr[lo] = middle;
        middle = arr[mid];
    }
    if(middle.compareTo(arr[hi]) > 0){
        arr[mid] = arr[hi];
        arr[hi] = middle;
        middle = arr[mid];
        if(arr[lo].compareTo(middle) > 0){
        arr[mid] = arr[lo];
        arr[lo] = middle;
        middle = arr[mid];
        }
    }
    int left = lo + 1;
    int right = hi - 1;
    if(left >= right)
        return;
    for( ;; ){
        while(arr[right].compareTo(middle ) > 0){
        right--;
        }
        while(left < right && arr[left].compareTo(middle) <= 0){
        left++;
        }
        if(left < right){
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        right--;
        }
        else{
        break;
        }
    }
    quicksort(arr, lo, left);
    quicksort(arr, left + 1, hi);
    }
}

So far so good. Jeg benytter binarySearch, der jo kræver at ens data er sorteret. Så derfor pre steppet quicksort, der sorterer data inden der søges i data. Hvad er så fordelen ved binarySearch ? da jeg jo alligevel i quicksort skal traverser alle elementer. Kan jeg så ikke i stedet for lave en ganske almindelig lineær søgning (for løkke) der loop igennem alle ikke sorterede elementer ? En anden ting er at den mængde data jeg gerne vil søge i ændre sig hele tiden(insert). Så er det måske mere hensigtsmæssigt at implementere et B+Træ ? og så lave en partial søgning i B+ træet ?

Prøv og kig på:

TreeMap<String,Integer>

Kode eksempel:

package september;

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Searching {
    public static void main(String[] args) {
        TreeMap<String,Integer> h = new TreeMap<String,Integer>();
        h.put("hello", new Integer(1));
        h.put("hell", new Integer(2));
        h.put("alpha", new Integer(3));
        h.put("bye", new Integer(4));
        h.put("hello2", new Integer(5));
        h.put("solly", new Integer(6));
        h.put("sally", new Integer(7));
        h.put("silly", new Integer(8));
        h.put("zorro", new Integer(9));
        h.put("hi", new Integer(10));
        SortedMap<String, Integer> h2 = h.subMap("h", "i");
        for(Entry<String,Integer> e : h2.entrySet()) {
            System.out.println(e.getKey() + " " + e.getValue());
        }
  }
}

arne>> super. Fandt ud af at fromKey < toKey så jeg kan f.eks. ikke skrive "i","h". Men hvordan får jeg den til at returnere alle forekomster startende med h. Jeg kan nemlig ikke skrive "h","h"

h.subMap("h", "i");

returnerer alle som starter med h

den finder nemlig alle key hvor "h" <= key < "i"

Arne>> Super Arne. Smider du et svar

Ups lige et lille spørgsmål. Hvis jeg nu vil søge på alle forekomster af hi, skal det så ikke være "hi", "hij" ?

Hov det skulle være "hi", "hj"

Jeps.

Og svar.

Strukturen skulle have nogle paene big O egenskaber.

TreeMap er implementeret som et Red-Black tree (binært søgetræ). Store O er O(log n).

Jeg er nu mere tilhængere af et B+ træ hvor store O (worst case) er ved:
Insert: O(logbn)
Search: O(logbn)
Delete: O(logbn)

Jeg kan godt lide at et B+ træ aldrig bliver særlige højt. Men fremfor selv at kode et B+ træ vil jeg benyttet mig af TreeMap der jo har en acceptabel store O.

Man bruger ikke B+ traer til in memory strukturer kun til on disk strukturer.

Binaere traer er hurtigere end multi traerer naar det er in memory strukturer.