Bitcoin Core maintains a LevelDB database (a key-value database) that contains the chain status data. This data includes the block headers, the block locations on disk, the UTXO set, and a few other things.
For blocks, the chainstate database has the block hashes as the key and block headers with some extra data appended as the values. The extra data also includes the block's location in the blk*.dat files (file number and byte offset within the file for the beginning of the block). So looking calling
getblock just means that the key-value pair for the block hash is taken from the LevelDB database which I believe is O(nlog(n)) (IIRC it uses some kind of tree as the backing structure). To get the block itself, the lookup is O(1) as it just has to read a specific file at a specific offset.
Very few RPC calls in Bitcoin Core actually do any sort of searching through the blockchain. Most things are either stored in a database or a reference to its location is stored in the database so the item itself can quickly be retrieved by or following a database read.