Das mit der Legende habe ich bereits gelöst. Interessant wäre noch
% -*- mode: latex; mode: flyspell; ispell-local-dictionary: "en_US"; coding: utf-8; fill-column: 80 -*-
\documentclass[a4paper,11pt,twoside,ngerman,color]{book}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{tikz,pgfplots}
\usepgfplotslibrary{groupplots}
\usetikzlibrary{snakes,shapes,arrows,matrix,positioning}
\pgfplotsset{compat=1.6}
\usetikzlibrary{pgfplots.groupplots}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\begin{groupplot}[group style={group name=myplot, group size=2 by 2, vertical sep=64pt, horizontal sep=12pt}, grid=both, grid style=dashed]
\nextgroupplot[title={\textbf{Durchsatz:} Erzeugung}, ylabel={Durchsatz [Mebibyte / Sekunde]}, xlabel={Elemente in der Datenstruktur [$\log_2(n)$]}]
\addplot coordinates { (25.0,27.2706) (26.0,27.6152) (27.0,27.0114) (28.0,25.4822) (29.0,23.6201) (30.0,18.3911) }; \label{plots:plot1}
\addplot coordinates { (25.0,19.4066) (26.0,21.0439) (27.0,24.2483) (28.0,25.7858) (29.0,25.2643) (30.0,23.2176) (31.0,21.5053) }; \label{plots:plot2}
\addplot coordinates { (25.0,25.8846) (26.0,25.6254) (27.0,24.5522) (28.0,23.8694) (29.0,22.3375) (30.0,18.2088) }; \label{plots:plot3}
\addplot coordinates { (25.0,20.732) (26.0,22.2468) (27.0,25.0059) (28.0,26.3556) (29.0,24.6092) (30.0,22.1791) (31.0,20.697) }; \label{plots:plot4}
\nextgroupplot[title={\textbf{Durchsatz:} Vorgängeranfrage}, yticklabel pos=right, xlabel={Elemente in der Datenstruktur [$\log_2(n)$]}, ylabel={Durchsatz [Millionen Anfragen / Sekunde]}]
\addplot coordinates { (25.0,2.197) (26.0,2.06646) (27.0,1.97961) (28.0,1.8256) (29.0,1.56041) (30.0,0.776778) };
\addplot coordinates { (25.0,3.15803) (26.0,2.24898) (27.0,2.12293) (28.0,1.98624) };
\addplot coordinates { (25.0,2.14384) (26.0,2.06185) (27.0,1.98044) (28.0,1.8621) (29.0,1.75767) (30.0,0.845749) };
\addplot coordinates { (25.0,3.00063) (26.0,2.43515) (27.0,2.11192) (28.0,2.04601) (31.0,0.887256) };
\nextgroupplot[title={\textbf{Speicherplatz:} Nach Erzeugung}, xlabel={Elemente in der Datenstruktur [$\log_2(n)$]}, ylabel={Speicherverbrauch [Gigabyte]}]
\addplot coordinates { (25.0,1.83424) (26.0,3.78422) (27.0,8.48936) (28.0,19.8347) (29.0,46.6281) (30.0,121.489) (31.0,254.124) };
\addplot coordinates { (25.0,3.06541) (26.0,5.35606) (27.0,8.42623) (28.0,15.1457) (29.0,31.0536) (30.0,68.7423) (31.0,153.308) };
\addplot coordinates { (25.0,1.80516) (26.0,3.71904) (27.0,8.28671) (28.0,19.1333) (29.0,44.2815) (30.0,114.652) (31.0,238.808) };
\addplot coordinates { (25.0,2.82335) (26.0,4.98529) (27.0,8.04859) (28.0,14.6836) (29.0,30.0445) (30.0,65.7417) (31.0,143.733) };
\nextgroupplot[title={\textbf{Speicherplatz:} Während Erzeugung}, yticklabel pos=right, xlabel={Elemente in der Datenstruktur [$\log_2(n)$]}, ylabel={Speicherverbrauch [Gigabyte]}]
\addplot coordinates { (25.0,1.83424) (26.0,3.78422) (27.0,8.48936) (28.0,19.8347) (29.0,46.6281) (30.0,121.489) (31.0,254.124) };
\addplot coordinates { (25.0,3.06541) (26.0,5.35606) (27.0,8.42623) (28.0,15.1457) (29.0,31.0536) (30.0,68.7423) (31.0,153.308) };
\addplot coordinates { (25.0,1.80516) (26.0,3.71904) (27.0,8.28671) (28.0,19.1333) (29.0,44.2815) (30.0,114.652) (31.0,238.808) };
\addplot coordinates { (25.0,2.82335) (26.0,4.98529) (27.0,8.04859) (28.0,14.6836) (29.0,30.0445) (30.0,65.7417) (31.0,143.733) };
\end{groupplot}
\path (myplot c1r1.outer north west)% plot in column 1 row 1
-- node[anchor=south,rotate=90] {Gleichverteilung}% label midway
(myplot c1r2.outer south west)% plot in column 1 row 4
;
%Legend
\path (myplot c1r1.north west|-current bounding box.north)--
coordinate(legendpos)
(myplot c2r1.north east|-current bounding box.north);
\matrix[
matrix of nodes,
anchor=south,
draw,
inner sep=0.2em,
draw
]at([yshift=1ex]legendpos)
{
\ref{plots:plot1}& 1&[5pt]
\ref{plots:plot2}&2&[5pt]
\ref{plots:plot3}& 3&[5pt]
\ref{plots:plot4}& 4\\
};
\end{tikzpicture}
\caption{...}
\label{plot:uniform_hm_u40}
\end{center}
\end{figure}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%