We address the problem of performing efficient spatial and topological queries on large tetrahedral meshes with arbitrary topology and complex boundaries. Such meshes arise in application domains such as 3D Geographic Information Systems (GISs), scientific visualization and finite element analysis. To this aim, we propose Tetrahedral trees, a family of spatial indexes based on a nested space subdivision (an octree or a kD-tree) and defined by several different subdivision criteria. We provide efficient algorithms for spatial and topological queries on Tetrahedral trees and compare to state-of-the-art approaches. Our results indicate that Tetrahedral trees are an improvement over R*-trees for querying tetrahedral meshes; they are more compact, they perform faster in many queries and are stable at variations of construction thresholds. They also support spatial queries on more general problem domains than topological data structures which explicitly encode adjacency information for efficient navigation, but have difficulties with non-trivial geometric or topological shapes.