A method and apparatus for partitioning a graph database that includes nodes connected to one another is presented. The method entails determining a node type indicating a type of node that is to be used as mapped nodes, and upon receiving a new node, placing the new node in a partition according to one or more property values associated with the new node if it is a mapped node, and placing the new node in a partition according to its connections to other nodes if it is not a mapped node. The apparatus includes modules containing computer-executable instructions to perform the above method.