Cos’è un indice

Pensiamo ad un libro (la nostra base dati) e immaginiamo di voler ricercare un argomento contraddistinto da una parola chiave (la chiave primria o esterna di una tabella). Possiamo scorrere il libro partendo dalla prima pagina fino a quando non troviamo l’argomento cercato (full scan) oppure possiamo avvalerci dell’indice analitico nel quale ad ogni argomento chiave è associata la pagina che lo tratta (chiave con il puntatore al record).

Gli incici sono delle strutture dati create dai database per permettere la ricerca efficiente e veloce dei record. Quando vengono poste delle condizioni sulla ricerca che coinvolgono campi con un indice è possibile, al posto di scandire integralmente una tabella (full scan), usare l’indice stesso per recuperare i record in modo più veloce e migliorando significativamente le prestazioni SQL.

Come è fatto un indice

Un indice ha solitamente una struttura ad albero dove ogni nodo dell’albero è una pagina contenente un insieme di chiavi. L’indice lo si può immaginare come un oggetto che divide la tabella in blocchi, ognuno dei quali contiene una lista dei valori chiave e indirizzi fisici (ROWIDs) delle righe nella basedati. In particolare vengono solitamente usati dei B-Tree (alberi bilanciati) che sono strutture dati ad albero con particolari caratteristiche.

B-Tree

Il B-Tree è una particolare struttura ad albero che eredita alcune caratteristiche dagli alberi di ricerca, infatti ogni chiave appartenente al sottonodo di sinistra sarà inferiore a quella della radice e ogni chiave del sottonododi destra avrà un valore superiore.

Sono inoltre dagli alberi bilanciati perché tutte le foglie si trovano alla stessa distanza rispetto alla radice. Uno dei principali vantaggi è che essi mantengono automaticamente i nodi bilanciati permettendo operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.

Un B-Tree di ordine n ha le seguenti caratteristiche:

• Tutti i nodi ad esclusione del nodo radice hanno da un minimo di n/2 (approssimato per difetto) a un massimo di n-1 chiavi.
• Un nodo con k chiavi avrà sempre k+1 rami (fattore di ramificazione)
• La radice contiene almeno una chiave
• In un nodo le chiavi sono ordinate secondo ordine crescente
• Ogni chiave punterà ad un record (o ad un insieme di record nel caso non sia una chiave primaria)
• Tutti i nodi foglia hanno la medesima profondità gerarchica

Se l’insieme delle chiavi è il seguente: {1,2,3,4,6,7,9,10,11,12,13,14,15,16,18,19,20,30,40,45,50,51,60,66}, possiamo avere un B-Tree come il seguente

E’ un B-Tree di ordine 4 con fattore di ramificazione massimo pari a 3 e profondità 3.

Supponiamo ora di voler ricercare il record che ha come chiave 34 e vediamo come verrà percorso l’albero:

Il processo di ricerca sarà al seguente:

• viene prima scandita la pagina del nodo radice nella quale non è contenuta la chiave
• visto che 34 è maggiore di 15 si passa sul ramo di destra
• viene scandito la pagina che ha chiavi 20 e 25 che non contiene la chiave cercata
• dato che 34 è maggiore di 20 e minore di 50 viene preso in considerazione il ramo centrale
• viene scandita la pagina con chiavi 30,40,45 che non contiene la chiave cercata
• la ricerca termina perchè la pagina ha tutti i puntatori nulli pertanto la chiave cercata non è stata trovata (come ci si aspettava)

Possiamo generalizzare la ricerca di una chiave come segue:

• Trasferimento in memoria della radice
• Ricerca di K nella pagina trasferita: se è presente, la ricerca è terminata.
• Altrimenti, se K è minore della chiave più a sinistra del nodo, allora trasferimento della pagina puntata dal puntatore di sinistra (se non è nullo); se K è maggiore della chiave più a destra allora trasferimento della pagina puntata dal puntatore più a destra (se non è nullo); se è compreso tra due chiavi del nodo allora trasferimento della pagina puntata dal puntatore compreso tra le due chiavi (se non è nullo). Ritorno al punto 2.
• Se il puntatore in questione è nullo, la chiave non è presente.

Ottimizzazioni e prestazioni

I B-Tree portano forti vantaggi in termini di velocità ed efficienza rispetto ad implementazioni alternative quando la maggior parte dei nodi si trova in una memoria secondaria, ad esempio in un disco fisso. Massimizzando il numero di nodi figli per ogni nodo, l’altezza dell’albero si riduce, l’operazione di bilanciamento è necessaria meno spesso e quindi l’efficienza aumenta. Generalmente questo numero è impostato in modo tale che ogni nodo occupi per intero un gruppo di settori: così, dato che le operazioni di basso livello accedono al disco per cluster, si minimizza il numero di accessi ad esso.

Il numero massimo di pagine da leggere per la ricerca coincide con l’altezza dell’albero. Poiché è possibile dimostrare che l’altezza dell’albero dipende dal logaritmo del numero di record del file, la lunghezza (o costo) della ricerca è una funzione logaritmica del numero di record del file. Il B-tree è inoltre tanto più conveniente quanto più il file è grande e la ricerca è più veloce tanto più sono piene le singole pagine. [1]

Riferimenti

[1] Autori Vari, “B-Albero“, Wikipedia, 2008

In database non molto recenti o che vengono ereditati da altri dbms può capitare di avere dei campi CHAR non correttamente utilizzati e che si vorrebbe sostituire con dei VARCHAR2.

Ricordo qual’è la differenza fra i diversi campi testuali:

• CHAR: servono per memorizzare stringhe di lunghezza fissa, se viene memorizzata una stringa più corta della lunghezza impostata verrà riempita in coda con degli spazi bianchi. Questo comporta una occupazione massiciia e spesso non voluta del disco.
• VARCHAR: attualmente hanno lo stesso scopo dei VARCHAR2 ma è un tipo riservato per scopi futuri, pertanto è consigliabile non utilizzarli.
• VARCHAR2: questa tipologia è usata per memorizzare stringhe di lunghezza variabile e che quindi ottimizzano, rispoetto ai CHAR, l’uso del disco.

Se si ha intenzione di convertire massicciamente i campi CHAR trasformandoli in VARCHAR2 di eguale capacità massima si può utilizzare il seguente script che genera le query di aggiornamento.

SELECT
	'ALTER TABLE ' || table_name ||
	' MODIFY ' || column_name ||
	' VARCHAR2(' || data_length || ');'
FROM
	sys.all_tab_cols
WHERE
	owner = 'OWNER_NAME'
	AND data_type = 'CHAR';

Questa query va a selezionare tutti i campi CHAR che appartengono a OWNER_NAME (da sostituire con il nome reale) e costruisce una serie di query di update come la seguente:

ALTER TABLE nome_tabella MODIFY nome_campo VARCHAR2(10);

E’ ormai molto di moda mostrare sulla SystemTray del nostro sistema operativo un’icona della nostra applicazione, magari con qualche simpatica opzione o magari solo quando l’applicazione è minimizzata.

Vediamo come questo può essere fatto utilizzando la classe SystemTray della libreria AWT presente dalla versione 6 di Java.

La classe SystemTray rappresenta la barra delle applicazioni della nostra scrivania. Questo concetto varia leggermente a seconda del sistema operativo che utilizziamo: su Microsoft Windows si riferisce alla “Taskbar Status Area”, su Gnome si intende “Notification Area”, su KDE è la “System Tray”.

Su alcuni sistemi operativi, o più genericamente dovremmo parlare di desktop environment, la System Tray potrebbe non esistere o non essere supportata in questo caso quando cercheremo di ottenere l’istanza dell SystemTray con il metodo getSystemTray() verrà sollevata l’eccezione UnsupportedOperationException.
Per testare se la barra è supportata basterà utilizzare il metodo isSupported().

La SystemTray può contenere più icone TrayIcon, aggiunt con il metodo add(java.awt.TrayIcon), e eliminate quando non più utili con remove(java.awt.TrayIcon). La classe TrayIcon consiste in un’immagine, un menù a popup e un insieme di listeners ad esso associati.

Vediamo come può essere utilizzata con un semplice esempio

/**
 *
 * @author Marco Fracassi
 */
import java.awt.AWTException;
import java.awt.Image;
import java.awt.MenuItem;
import java.awt.PopupMenu;
import java.awt.SystemTray;
import java.awt.Toolkit;
import java.awt.TrayIcon;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JOptionPane;

public class UsingSysTray {

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

        if (!SystemTray.isSupported()) {
            System.out.println("La SystemTray non è supportata");
            return;
        }

        SystemTray tray = SystemTray.getSystemTray();
        Toolkit toolkit = Toolkit.getDefaultToolkit();
        Image image = toolkit.getImage("trayIcon.jpg");

        PopupMenu menu = new PopupMenu();

        MenuItem messageItem = new MenuItem("Mostra messaggio");
        messageItem.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e) {
                JOptionPane.showMessageDialog(null, "www.itcsp.it");
            }
        });
        menu.add(messageItem);

        MenuItem closeItem = new MenuItem("Chiudi");
        closeItem.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e) {
                System.exit(0);
            }
        });
        menu.add(closeItem);

        TrayIcon icon = new TrayIcon(image, "SystemTray itcsp", menu);
        icon.setImageAutoSize(true);
        try {
            tray.add(icon);
        } catch (AWTException e) {
            System.out.println("La TrayIcon non può essere aggiunta");
        }
    }
}