The k 2 -tree compact data structure has gained great popularity to represent binary relationships in main memory. It presents a good performance and a good trade-off between storage and execution time. However, datasets being too large, or limited resources, may prevent the dataset from fitting into RAM even in compressed form. This work presents an experimental evaluation of a k 2 -tree in external memory (disk), in terms data access (I/O operation or cache misses) and execution time for 4 types of common queries. We compare the k 2 -tree with other data structures, namely a Quadtree (specifically, a Linear QuadTree, LQT) and the classical adjacency matrix, all of them being in external memory. We used for the test both synthetical as well as large, real world, datasets. Several aspects, such as the size of the memory buffer and its replacement scheme, or specific parameters like the arity ( k value) of the k 2 -tree were considered in the experiments. In terms of storage needs, the k 2 -tree clearly outperforms the other alternatives, in extreme cases needing only 1% of the LQT space, or 0.01% of the adjacency matrix (and for some large datasets neither the LQT nor the adjacency matrix could be built). In terms of performance, except for cases with small datasets, where the adjacency matrix is the best option for some queries, the k 2 -tree is either competitive or outperforms the alternatives.