Data marketplaces (DMs) promote the benefits of the Internet of Things (IoT) in smart cities. To facilitate the easy exchanges of real-time IoT data streams between device owners and third-party applications, it is required to provide scalable, interoperable, and secured services for large numbers of distributed IoT devices operated by different application vendors. Thanks to decentralization, immutability, and auditability, Blockchain is promising to enable a tamper-proof and trust-free framework to enhance performance and security issues in centralized DMs. However, directly integrating blockchains into large-scale IoT-based DMs still faces many limitations, such as high resource and energy demands, low transaction throughput, poor scalability, and challenges in privacy preservation. This paper introduces a novel Federated Ledgers-based Framework for Hierarchical Decentralized Data Marketplaces (Fed-DDM). In Fed-DDM, participants are divided into multiple permissioned domains given their registrations. Each domain leverages an efficient Byzantine Fault Tolerance (BFT) consensus protocol to commit transactions of a domain on a private intra-ledger. A public inter-ledger network adopts a scalable Proof-of-Work (PoW) consensus protocol to federate multiple private intra-ledger networks. We design a smart contract-enabled inter-ledger protocol to guarantee the security of the cross-domain operations on a public federated ledger without exposing sensitive privacy information from private ledgers. A proof-of-concept prototype is implemented, and the experimental results verify the feasibility of the proposed Fed-DDM solution with performance and security guarantees.