Graafitietokanta on tietokanta, jossa tietoa varastoidaan solmuihin (engl. nodes) ja niiden välisiin suhteisiin (engl. relationships).[1] Muodollisesti graafi on kokoelma solmuja (engl. vertices) ja kaaria (engl. edges).[1]
Näin ollen rakenne muodostaa graafin, josta myös nimi. Oleellinen osa graafitietokantoja on myös kyselykieli jolla tietoa haetaan tietokannasta. Toisin kuin relaatiomalliin perustuvissa tietokannoissa kyselykieleksi vakiintunut SQL, ei graafitietokannoilla ole vastaavaa standardisoitua kyselykieltä.